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
难度：easy
题目：给定仅包含字符 '(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ 和 ‘]’ 的字符串, 判定这个字符串是否有效。输入字符串是否有效：开括号必需与同类型括号关闭。开括号必需要以正确的顺序关闭。注意 空字符串被认为是有效的字符串。
思路：stack
Runtime: 5 ms, faster than 74.68% of Java online submissions for Valid Parentheses.Memory Usage: 26.3 MB, less than 52.20% of Java online submissions for Valid Parentheses.
class Solution {
public boolean isValid(String s) {
// stack
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ‘(‘) {
stack.push(‘)’);
} else if (c == ‘{‘) {
stack.push(‘}’);
} else if (c == ‘[‘) {
stack.push(‘]’);
} else {
if (stack.isEmpty() || stack.pop() != c) {
return false;
}
}
}
return stack.isEmpty();
}
}