题目
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
解法思路（一）
解法描述
- 对于待判断的字符串，逐字符的判断；
- 如果属于左括号，就压入栈中；
- 如果属于右括号，就和栈顶的左括号比较，当然，前提是栈不为空；
- 如果栈顶左括号和待比较的右括号不匹配，那么这个字符串就是非法的；
- 如果最后一个右括号也能和栈顶的左括号匹配，那么就得看栈中还有没有左括号剩余，没剩余，待判断的字符串才是合法的；
解法实现（一）
关键字
栈 括号匹配
代码实现
import java.util.Stack;
class Solution20_1 {
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();
}
}
