image

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例如下：

s = "()[]{}" // 结果为true
s = "{[]}"   // 结果为true
s = "([)]"   // 结果为false
s = "(}"         // 结果为false

1. 第一种解法 while & replace

这是最容易的一种解法，我相信屏幕前的各位都能很轻松的想到。这也是我提交的第一种解法，但是结果却令我很惊讶，不是没有通过测试，而是执行用时和内存消耗都菜的可怜（执行结果我就不贴出来了😂）。

public boolean isValid(String s) {
    while (s.contains("()") || s.contains("[]") || s.contains("{}")) {
        if (s.contains("()")) {
            s = s.replace("()", "");
        }
        if (s.contains("{}")) {
            s = s.replace("{}", "");
        }
        if (s.contains("[]")) {
            s = s.replace("[]", "");
        }
    }
    return s.length() == 0;
}

2. 第二种解法 stack 解法

栈解法的结题思路是 遇到左括号push，遇到右括号pop，然后用pop的返回值进行比较。另外需要注意一下特殊条件就OK了，也挺简单的。

public static boolean isValid(String s) {
    int stackSize = s.length() >> 1;
    if (stackSize * 2 != s.length()) return false;
    
    Stack<Character> stack = new Stack<Character>();
    for (int i = 0; i < s.length(); i++) {
        char one = s.charAt(i);
        if (one == '(' || one == '[' || one == '{') {
            stack.push(one);
        } else {
            if (stack.isEmpty()) {
                return false;
            }
            char pop = stack.pop();
            if (pop == '(' && one != ')') return false;
            if (pop == '[' && one != ']') return false;
            if (pop == '{' && one != '}') return false;
        }
    }
    return stack.isEmpty();
}

3. 第三种解法 HashMap 解法

这种解法和第二种解法相差不多，其中思路都是相同的。优点在于不用循环创建零时变量，减少内存消耗。提交结果也证明了这一点，在所有 Java 提交中击败了84.04%的用户。

public boolean isValid2(String s) {
    HashMap<Character, Character> map = new HashMap<>();
    map.put('(', ')');
    map.put('[', ']');
    map.put('{', '}');
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (map.containsKey(c)) {
            stack.push(c);
        } else {
            if (stack.isEmpty() || map.get(stack.pop()) != c) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

4. 第四种解法 StackPro 解法

啥叫 StackPro？哈哈，就是很牛逼的 Stack 啊。下面是 二蛋 给出的白话文翻译：

// 1. 如果满足是左括号，就push一个右括号入栈。所以第四个判断肯定是右括号
// 2. 如果到第四个判断 stack 是空的话，说明s的第一个值肯定是右括号，不满足直接返回false。
// 3. 到第四个判断不是空的话，则必须要和栈顶元素相同，所以pop后返回的值如果不等于c，则不满足要求返回false
// 4. 最后一种情况，如果右括号没有左括号多，则stack肯定不会pop完，所以直接 return stack.isEmpty()
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() || c != stack.pop()) {
            return false;
        }
    }
    return stack.isEmpty();
}

哈哈，StackPro解法强不强图片？

声明：文章来源自公众号 程序员二蛋