对LeetCode 20有效括号一种另类Java解法的困惑

问题说明 #

LeetCode 20题要求判断仅包含'(', ')', '{', '}', '[', ']'的字符串是否为有效括号串，有效条件为：

• 开括号必须由相同类型的闭括号闭合
• 开括号必须按正确顺序闭合

以下是该题的一种另类解法：

class Solution {
    public boolean isValid(String s) {
        int len = s.length() / 2;

        for (int i = 0; i < len; i++) {
            s = s.replace("()", "").replace("{}", "").replace("[]", "");
        }

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

疑问与解答 #

困惑点 #

输入如"([{}])"时该解法仍能生效，但replace()是按顺序扫描字符串的，无法理解其原理。

原理拆解 #

这种解法的核心是反复消除所有相邻的有效括号对，直到无法消除为止，最终字符串为空则说明原串有效。

针对"([{}])"的具体执行过程：

1. 第一次循环：扫描"([{}])"，replace("()")找不到匹配；replace("{}")会找到中间的"{}"，替换后字符串变为"([])"；replace("[]")此时无相邻匹配，当前串为"([])"。
2. 第二次循环：扫描"([])"，replace("()")无匹配；replace("{}")无匹配；replace("[]")找到中间的"[]"，替换后字符串变为"()"。
3. 第三次循环（原串长度为6，len=3，循环3次）：扫描"()"，替换后字符串变为空。

最终字符串长度为0，返回true，符合有效条件。

关键要注意：String.replace()方法会替换字符串中所有匹配的子串，而非仅第一个。哪怕最内层的括号先被消除，外层括号会逐渐变成相邻的有效对，在下一轮循环中被处理。

循环次数设为原长度的一半也很合理：有效括号串每消除一对，长度减少2，最多需要length/2次循环就能完成所有消除操作。

内容的提问来源于stack exchange，提问作者Yile Feng