力扣LeetCode：20. 有效的括号（Python、 Java）

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

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

经典的栈结构的应用。具体的算法流程是：

• 定义一个用于辅助的栈。
• 自左向右遍历字符串中的每一个字符：
  • 若为左括号，入栈。
  • 若为右括号，判断其与栈顶元素是否匹配。
    • 若匹配，则栈顶元素出栈。
    • 若不匹配，则直接判断False。
    • 若栈为空，则直接判断False。
• 若最终栈为空栈，则为True，否则为False。

具体实现上，有一些技巧：

• 判断左右括号是否匹配时，可以使用字典，或是根据ASCII值（ord方法）。
  • 小括号：右括号比左括号的ASCII大1。
  • 中括号、大括号：右括号比左括号的ASCII大2。
• 若字符串长度为奇数，则必然无效，不必遍历。

这是2020年1月写的代码，因为现在已经很少用Java了，所以暂时没有进一步改进：

class Solution {
	char f(char c) {
		if(c==']')
			return '[';
		if(c==')')
			return '(';
		if(c=='}')
			return '{';
		return ' ';
	}
    public boolean isValid(String s) {
        Stack stack=new Stack();
        for(int i=0; i
            if(stack.empty()) {
            	stack.push(s.charAt(i));
            	continue;
            }
            if(f(s.charAt(i))!=' '&&(char)stack.peek()==f(s.charAt(i))) {
            	stack.pop();
            	continue;
            }
            stack.push(s.charAt(i));
        }
        return stack.isEmpty();
    }
}

这是2020年1月写下的代码：

class Solution(object):
    def isValid(self, s):
        lst=[]
        for i in s:
            if i=='(' or i=='{' or i=='[':
                lst.append(i)
            else:
                if len(lst)==0:
                    return False
                if (i==')' and lst[-1]!='(') or (i==']' and lst[-1]!='[') or (i=='}' and lst[-1]!='{'):
                    return False
                lst.pop()
        return len(lst)==0

这是2022年4月写下的代码：

class Solution(object):
    def isValid(self, s):
        if len(s) % 2 == 1:
            return False
        stack = []
        for ch in s:
            if ch in ['(', '[', '{']:
                stack.append(ch)
            else:
                if not stack or abs(ord(stack[-1]) - ord(ch)) > 2:
                    return False
                stack.pop()
        return not stack

受题解启发，找到了另外一种非常有趣的算法。具体流程是这样的：不断消去字符串中的’()‘、’[]‘、’{}'子串，直至不存在这些子串。此时，如果字符串为空，代表有效。

该算法效率不高，但非常巧妙，且代码非常优美。

class Solution(object):
    def isValid(self, s):
        while True:
            pre_len = len(s)
            s = s.replace('()', '')
            s = s.replace('[]', '')
            s = s.replace('{}', '')
            if len(s) == pre_len:
                return pre_len == 0