做題筆記：Valid Parentheses (Java)
題目描述：
給定一個僅包含字符 '(', ')', '{', '}', '[' 和 ']' 的字符串 s，確定輸入字符串是否有效。
有效的情況指：
- 前括號必須用相同類型的括號閉合。
- 前括號必須以正確的順序閉合。
Example 1:
Input: s = "()"
Output: trueExample 2:
Input: s = "()[]{}"
Output: trueExample 3:
Input: s = "(]"
Output: false暴力解法：
昨天半夜擼的，還是想不到什麼好點子：
class Solution {
public boolean isValid(String s) {
StringBuilder sb = new StringBuilder();
sb.append(s);
for(int i = 0; i<sb.length()-1; i++ ){
if ( (sb.charAt(i) == '(' && sb.charAt(i+1) == ')') ||
(sb.charAt(i) == '[' && sb.charAt(i+1) == ']') ||
(sb.charAt(i) == '{' && sb.charAt(i+1) == '}')
){
sb = sb.deleteCharAt(i+1);
sb = sb.deleteCharAt(i);
i = -1;
}
}
if (sb.toString() == ""){
return true;
}
else{
return false;
}
}
}79 ms，慘不忍睹。
Stack 解法：
Hint 中已經提到，應該使用 Stack ：
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
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();
}
}2 ms