做題筆記：Valid Parentheses (Java)

題目描述：

給定一個僅包含字符 '(', ')', '{', '}', '[' 和 ']' 的字符串 s，確定輸入字符串是否有效。

有效的情況指：

1. 前括號必須用相同類型的括號閉合。
2. 前括號必須以正確的順序閉合。

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 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