20. 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.

链接：http://leetcode.com/problems/valid-parentheses/

题解： 一道基本的使用stack的题目。 Time Complexity - O(n)， Space Complexity - O(n)

public class Solution {
    public boolean isValid(String s) {
        if(s == null || s.length() == 0)
            return true;
        Stack<Character> stack = new Stack<Character>();
        
        for(int i = 0; i < s.length(); i ++){
            int left = s.charAt(i);
            if(left == '(' || left == '[' || left == '{') 
                stack.push(s.charAt(i));
            else {
                if(stack.isEmpty())
                    return false;
                char right = stack.pop(); 
                if(left == ']' && right != '[')
                    return false;
                else if(left == '}' && right != '{')
                    return false;
                else if (left == ')' && right != '(')
                    return false;
            }
        }
        
        if(!stack.isEmpty())
            return false;
        return true;
    }
}

二刷：

Java:

这里在想以后要不要把所有的stack都换成linkedlist，因为stack继承自vector，linkedlist继承自list，而vector以后可能会用得很少。

public class Solution {
    public boolean isValid(String s) {
        if (s == null) {
            return false;
        }
        if (s.length() == 0) {
            return true;
        }
        LinkedList<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ']' || c == '}' || c == ')') {
                if (stack.size() == 0) {
                    return false;
                } else {
                    char openChar = stack.removeLast();
                    if ((c == ']' && openChar != '[') || (c == '}' && openChar != '{') || (c == ')' && openChar != '(')) {
                        return false;
                    }
                }
            } else {
                stack.add(c);
            }
        }
        return stack.size() == 0;
    }
}

Python:

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for i in range(0, len(s)):
            c = s[i]
            if c == ']' or c == '}' or c == ')':
                if stack == []:
                    return False
                openChar = stack.pop()
                if (c == ']' and openChar != '[') or (c == '}' and openChar != '{') or (c == ')' and openChar != '('):
                    return False
            else:
                stack.append(c)
        return stack == []
        

三刷:

写得还是不漂亮， 究竟多个或操作该怎么换行才能优雅好看??

Java:

public class Solution {
    public boolean isValid(String s) {
        if (s == null) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '{' || c == '[' || c == '(') {
                stack.push(c);
            } else if (stack.isEmpty()) {
                return false;
            } else {
                char oChar = stack.pop();
                if ((c == '}' && oChar != '{') || (c == ']' && oChar != '[') || (c == ')' && oChar != '(')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

Reference:

https://leetcode.com/discuss/26445/12-lines-of-java