题目
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.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
解法思路（一）
- 遍历字符串中的所有字符，如果属于左括号，就将其压入一个栈中；
- 如果属于右括号，就拿其和栈顶字符比较，如果栈为空，返回 false；如果匹配失败，返回 false；
- 遍历完成后，看栈是否为空，为空返回 true；不为空，返回 false；
解法实现（一）
时间复杂度
- O(s.length)；
空间复杂度
- O(s.length)；
关键字
栈 括号匹配
实现细节
- 注意在弹出栈顶元素时，要确保栈中还有元素可弹；
package leetcode._20;
import java.util.Stack;
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
if (c == ')' && top != '(') {
return false;
}
if (c == ']' && top != '[') {
return false;
}
if (c == '}' && top != '{') {
return false;
}
}
}
return stack.isEmpty();
}
}
