image

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合译红。

示例如下：

s = "()[]{}" // 結(jié)果為true
s = "{[]}"   // 結(jié)果為true
s = "([)]"   // 結(jié)果為false
s = "(}"         // 結(jié)果為false

1. 第一種解法 while & replace

這是最容易的一種解法预茄，我相信屏幕前的各位都能很輕松的想到。這也是我提交的第一種解法侦厚，但是結(jié)果卻令我很驚訝耻陕，不是沒有通過測試，而是執(zhí)行用時和內(nèi)存消耗都菜的可憐（執(zhí)行結(jié)果我就不貼出來了??）刨沦。

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 解法

棧解法的結(jié)題思路是 遇到左括號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 解法

這種解法和第二種解法相差不多来破，其中思路都是相同的篮灼。優(yōu)點在于不用循環(huán)創(chuàng)建零時變量，減少內(nèi)存消耗徘禁。提交結(jié)果也證明了這一點诅诱，在所有 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解法強不強圖片赢底？

聲明：文章來源自公眾號 程序員二蛋