来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses/
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
题目分析
栈：先进后出
思路：
- 字符串长度必定为偶数，若为奇数直接返回false（即括号无效）；
- 遍历字符串，遇到左括号放入栈；
- 遇到右括号时，取栈顶元素（空 or 左括号）比较。若为空，直接返回false，若为左括号判断与该右括号是否相同类型；
- 类型相同，继续遍历；类型不同，直接返回false
代码实现
public class Valid20 {
public static void main(String[] args) {
Valid20 valid20 = new Valid20();
boolean result = valid20.isValid("()[]{}");
System.out.println(result);
}
/**
* 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
* <p>
* 有效字符串需满足：
* <p>
* 左括号必须用相同类型的右括号闭合。
* 左括号必须以正确的顺序闭合。
*
* @param s
* @return
*/
public boolean isValid(String s) {
int n = s.length();
// 奇数不满足
if (n % 2 != 0) {
return false;
}
// 存放右括号
Map<Character, Character> map = new HashMap<Character, Character>();
map.put(')', '(');
map.put('}', '{');
map.put(']', '[');
// 栈，先进后出，存放左括号
LinkedList<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if(!map.containsKey(ch)){
stack.addLast(ch);
} else {
if(stack.isEmpty() || stack.getLast() != map.get(ch)){
return false;
}
stack.removeLast();
}
}
return stack.isEmpty();
}
}
复杂度
- 时间复杂度：O(logn)，其中 n 是定版本的数量。
- 空间复杂度：O(1)，只需要常数的空间保存变量。
好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！
�
