题目
本题为leetcode探索初级算法中其它章节的一题
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnbcaj/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
我的解法
class Solution {
public static boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
char[] chars = s.toCharArray();
for (char aChar : chars) {
if(aChar == '(' || aChar == '{' || aChar == '['){
stack.push(aChar);
}
if(aChar == ']'){
if(stack.isEmpty()){
return false;
}
Character pop = stack.pop();
if(pop == null || !pop.equals('[')){
return false;
}
}
if( aChar == '}'){
if(stack.isEmpty()){
return false;
}
Character pop = stack.pop();
if(pop == null || !pop.equals('{')){
return false;
}
}
if(aChar == ')'){
if(stack.isEmpty()){
return false;
}
Character pop = stack.pop();
if(pop == null || !pop.equals('(')){
return false;
}
}
}
return stack.isEmpty();
}
}
这道题想到用栈,问题就不大了。
官方解法
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}
时间复杂度:O(n)O(n),其中 nn 是字符串 ss 的长度。
空间复杂度:O(n + |\Sigma|)O(n+∣Σ∣),其中 \SigmaΣ 表示字符集,本题中字符串只包含 66 种括号,|\Sigma| = 6∣Σ∣=6。栈中的字符数量为 O(n)O(n),而哈希映射使用的空间为 O(|\Sigma|)O(∣Σ∣),相加即可得到总空间复杂度。
与官方相比大致思路相同,官方中先判断了长度,题目中前提是“只包括”所以长度为奇数肯定是false。
另外用到了map简化了if-else判断。