Leetcode#20 Valid Parentheses

Posted on | In
leetcode solutions (through java)

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Soluion 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean isValid(String s) {
        Stack<Character> parentheses = new Stack<Character>();
        for(int i=0;i<s.length();++i){
            char c = s.charAt(i);
            if(c=='('||c=='['||c=='{') 
                parentheses.push(c);
            else{
                if(parentheses.empty())
                    return false;
                if(c==')'&&parentheses.peek()!='(')
                    return false;
                if(c==']'&&parentheses.peek()!='[')
                    return false;
                if(c=='}'&&parentheses.peek()!='{')
                    return false;
                parentheses.pop();
            }
        }
        return parentheses.empty();
    }
}

Solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/** 
     * 这个方法超棒 
     * 栈中放的只有当前需要出现的右部 
     * 当出现一个左部的时候，就将应该出现的右部放入栈中 
     * 当出现右部时和栈顶元素比较，如果不相同则返回FALSE 
     * 最后栈为非空时也会返回FALSE 
**/ 

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();  
        for (char c : s.toCharArray()) {  
            if (c == '(')  
                stack.push(')');  
            else if (c == '{')  
                stack.push('}');  
            else if (c == '[')  
                stack.push(']');  
            else if (stack.isEmpty() || stack.pop() != c)  
                return false;  
        }  
        return stack.isEmpty();  
    }
}