给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串,判断字符串是否有效。
Given a string containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
注意空字符串可被认为是有效字符串。
Note that an empty string is also considered valid.
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
解题思路:
很简单的题,将字符串每个字符压入栈,简单判断即可。如:
输入: "{[]}"
初始栈为空,'{' 入栈
下一个字符
栈顶元素 '{' 与 '[' 不匹配,'[' 入栈
下一个字符
栈顶元素 '[' 与 ']' 匹配,'[' 出栈
下一个字符
栈顶元素 '{' 与 '}' 匹配,'}' 出栈
结束,栈为空,返回 True
关键在于判断字符是否匹配,匹配的标准是相反的括号字符,并非相同字符。可以用 switch 判断三种括号字符,或者三个 if 语句,再或者可以用散列表映射括号关系。
Java:
class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();// 初始化栈
for (char b : s.toCharArray()) {switch (b) {
case '(': {stack.push(')');
break;
}
case '{': {stack.push('}');
break;
}
case '[': {stack.push(']');
break;
}
default: {// 不匹配的情况返回 false
if (stack.isEmpty() || stack.pop() != b) {return false;}
}
}
}
return stack.isEmpty();// 栈为空则证明全部匹配,返回 true,否则返回 false}
}
Python:
注:python 中没有 switch…case… 语句,官方让用 if 判断代替 …
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for c in s:
if c == '[':
stack.append(']')
elif c == '(':
stack.append(')')
elif c == '{':
stack.append('}')
elif len(stack) == 0 or stack.pop() != c:
return False
return len(stack) == 0
欢迎关注微信公. 众号:爱写 Bug