Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

SOLUTION1:

使用stack来解决的简单题目。所有的字符依次入栈

1. 遇到成对的括号弹栈，弹栈不成对返回false.

2. 栈为空只能压入左括号

3. 扫描完成时，栈应该为空，否则返回FALSE.

SOLUTION 2:

使用堆栈解决，比较简单。push右括号时，检查左括号在不在，如果不在，返回false,否则弹出一个左括号。

最后看栈是否为空，不为空代表括号数不对称，也要返回false;

 public class Solution {

     public boolean isValid(String s) {

         if (s == null) {

             return false;

         }

         int len = s.length();

         // bug 1: don't use s as the name of the stack.

         Stack<Character> stk = new Stack<Character>();

         for (int i = 0; i < len; i++) {

             char c = s.charAt(i);

             switch(c) {

                 case '(':

                 case '[':

                 case '{':

                     stk.push(c);

                     break;

                 case ')':

                     if (!stk.isEmpty() && stk.peek() == '(') {

                         stk.pop();

                     } else {

                         return false;

                     }

                     break;

                 case '}':

                     if (!stk.isEmpty() && stk.peek() == '{') {

                         stk.pop();

                     } else {

                         return false;

                     }

                     break;

                 case ']':

                     if (!stk.isEmpty() && stk.peek() == '[') {

                         stk.pop();

                     } else {

                         return false;

                     }

                     break;

             }

         }

         return stk.isEmpty();

     }

 }

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/stack/IsValid.java

巴特西

LeetCode: Valid Parentheses 解题报告

Valid Parentheses

SOLUTION1:

SOLUTION 2:

最新文章

热门文章