[LeetCode] 20. Valid Parentheses 解題思路 (Easy)

這題需要判斷括號是否都成對。

LeetCode 題目連結

 

https://leetcode.com/problems/valid-parentheses/

題目

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. 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

Accept 作法

這題時間複雜度 O(n)，展現 Stack 先進後出的特性。


Runtime: 1 ms
Memory: 37.4 MB

Java 程式碼

class Solution {
    public boolean isValid(String s) {
        Stack stack = new Stack();
        for(int i = 0; i<s.length();i++){
            char ch = s.charAt(i);
            
            if(stack.size() == 0 || ch == '(' || ch == '[' || ch == '{'){
               stack.push(ch); 
                continue;
            }
            
            char chPop = (char)stack.peek();
            if(ch ==')' && chPop == '('){
                stack.pop();
            }else if(ch ==']' && chPop == '['){
                stack.pop();
            }else if(ch =='}' && chPop == '{'){
                stack.pop();
            }else{
                stack.push(ch);
            }
            
            
        }
        
        return stack.size() == 0;
    }
}

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題