ValidParentheses [source code]

public class ValidParentheses {
static
/******************************************************************************/
public class Solution {
    public boolean isValid(String s) {
        if (s.length() == 0 || s.length() % 2 != 0) return false;
        char[] chs = s.toCharArray();
        char[] map = new char[256];
        map[')'] = '(';
        map[']'] = '[';
        map['}'] = '{';
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < chs.length; i++) {
            if (map[chs[i]] == 0) {
                stack.push(chs[i]);
            } else {
                if (stack.empty() || stack.peek() != map[chs[i]]) return false;
                stack.pop();
            }
        }
        return stack.empty();
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ValidParentheses.Solution tester = new ValidParentheses.Solution();
        String[] inputs = {
            "()", //true
            "()[]{}", //true
            "([)]", //false
            "([])", //true
            "((", //false
        };
        for (String s : inputs) System.out.println(s + " -> " + tester.isValid(s));
    }
}

其实是一个非常简单的问题, 不过我对 Stack 不太熟悉, 所以还是花了太多的时间; 最后的速度是11ms (40%), 不算快. 当然这个题目想要加速的话, 其实也是很简单的, 比如这里的 Stack 可以用一个 array 来做. 不过暂时就不搞这种 trivial 的 optimization了. //稍微改了一下, 有8(92)了, 不知道什么情况;

看了一下, submission 上面最快的几个, 果然都是直接用 array 来做 Stack 的, 看看就行了, 如果以后有时间, 自己再来实现, 现在不纠结这种小细节;

stream 算法的末尾处理

这个吃亏不是一回两回了, 这一题我想到了开头的地方要有特殊的检查(stack 还是空的时候, 就直接来一个右括号), 但是没有想到末尾的检查. 这个就是左括号太多的情况, 也要考虑, 这个只要在stream end加一个检查就行了;

这个是 discussion 最优解:

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();  
}

思路其实都是一样的, 不过他这个简练很多. 我这里刚开始的做一个hash array 之类的这个操作其实并没有什么实际的必要, 因为这里的 可能性太少了;

反正这题一个稍微值得注意的优化点就是不能来左括号你就 push 左括号, 而应该 push 右括号, 这样后面查询的代码可以统一成一个 branch(因为不用考虑不同的 literal 了);

以前还讲过用 string 来做 Map 的思路, 这里是一个版本:

public class Solution {  
    public boolean isValid(String s) {  
        Stack<Integer> p = new Stack<>();  
        for(int i = 0; i < s.length(); i++) {  
            int q = "(){}[]".indexOf(s.substring(i, i + 1));  
            if(q % 2 == 1) {  
                if(p.isEmpty() || p.pop() != q - 1) return false;  
            } else p.push(q);  
        }  
        return p.isEmpty();  
    }  
}

大概看看就行, 也是比较蛋疼的东西; 除了简化代码以外一无是处;

这个是一个更加奇葩的 string-based 的答案:

public class Solution {  
    public boolean isValid(String s) {  
        int length;  

        do {  
            length = s.length();  
            s = s.replace("()", "").replace("{}", "").replace("[]", "");  
        } while(length != s.length());  

        return s.length() == 0;  
    }  
}

而且这个代码的速度估计还不会很好;

下面的人对这个代码的意见:
Nooooo! Stop upvoting it....

In an algorithms coding community who appreciates constructing 3*n/2 separate String objects to validate a single String? Not to mention that each replace call uses regex:

• compiles a Pattern
• creates a Matcher
• builds the replacement using a StringBuffer ("synchronized StringBuilder")
  Don't get me wrong, regex is awesome, I love it, and use it very often for parsing complex structures. The difference is that for some tasks there are faster ways. Just because a code has less characters it doesn't mean it's better. My outburst is highly correlated to using a regex without knowing it or knowingly in a loop that isn't pre-compiled. Consider the following code:

public class Solution {  
    private static final Pattern PARENS = Pattern.compile("\\(\\)|\\[\\]|\\{\\}");  
    public boolean isValid(String s) {  
        int length;  
        do {  
            length = s.length();  
            s = PARENS.matcher(s).replaceAll("");  
        } while (length != s.length());  
        return s.isEmpty();  
    }  
}

same result, 1 regex = 1 compile overall, 1 extra string created per iteration; still using StringBuffer though. I would be happier with this, but there's still a way to do it by iterating over the characters of the input once.

意思是这个代码其实速度比你想象的还要糟糕的多;

Problem Description

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.

Difficulty:Easy
Total Accepted:210.1K
Total Submissions:632K
Contributor: LeetCode
Companies
google airbnb facebook twitter zenefits amazon microsoft bloomberg
Related Topics
stack string
Similar Questions
Generate Parentheses Longest Valid Parentheses Remove Invalid Parentheses