题目描述
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
题解
经典的栈结构的应用。具体的算法流程是：
- 定义一个用于辅助的栈。
- 自左向右遍历字符串中的每一个字符：
- 若为左括号，入栈。
- 若为右括号，判断其与栈顶元素是否匹配。
- 若匹配，则栈顶元素出栈。
- 若不匹配，则直接判断False。
- 若栈为空，则直接判断False。
- 若最终栈为空栈，则为True，否则为False。
具体实现上，有一些技巧：
- 判断左右括号是否匹配时，可以使用字典，或是根据ASCII值（ord方法）。
- 小括号：右括号比左括号的ASCII大1。
- 中括号、大括号：右括号比左括号的ASCII大2。
- 若字符串长度为奇数，则必然无效，不必遍历。
Java代码
这是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<s.length(); 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();
}
}
Python代码
这是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
What’s more
受题解启发，找到了另外一种非常有趣的算法。具体流程是这样的：不断消去字符串中的’()‘、’[]‘、’{}'子串，直至不存在这些子串。此时，如果字符串为空，代表有效。
该算法效率不高，但非常巧妙，且代码非常优美。
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
