20. Valid Parentheses Solved

20. Valid Parentheses

難度: Easy

類型: String, Stack

CPP程式下載: 20.cpp

前情題要:

檢查字串是否括弧對稱正確。

Given a string s 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.
3. Every close bracket has a corresponding open bracket of the same type.

 

Example 1:

Input: s = "()"

Output: true

Example 2:

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

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

 

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

思考方式:

後進先出, 用 Stack 實作

複雜度思考:

Time Complexity: O( N ) 

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 8.56 MB, Beats: 96.45%

Accepted

100 / 100 testcases passed

tendchen

submitted at Jul 10, 2025 20:59

Runtime

0ms

Beats100.00%

Analyze Complexity

Memory

8.56MB

Beats96.45%

Analyze Complexity

Code

C++

class Solution {
public:
    bool isValid(string s) {
        int i;
        int len=s.size();
        stack<char> sc_symbol;
        //cout << len;
        for (i=0;i<len;i++)
        {
            switch(s[i])
            {
                case '(':
                case '[':
                case '{':
                    sc_symbol.push(s[i]);
                    break;
                case ')':
                    if (sc_symbol.empty()) return false;
                    //cout << sc_symbol.pop();
                    //printf("char=%c\n",sc_symbol.top());
                    if (sc_symbol.top()!='(') return false;
                    sc_symbol.pop();
                    break;
                case ']':
                    if (sc_symbol.empty()) return false;
                    //printf("char=%c\n",sc_symbol.top());
                    if (sc_symbol.top()!='[') return false;
                    sc_symbol.pop();
                    break;
                case '}':
                    if (sc_symbol.empty()) return false;
                    //printf("char=%c\n",sc_symbol.top());
                    if (sc_symbol.top()!='{') return false;
                    sc_symbol.pop();
                    break;

            }
        }
        if (sc_symbol.empty()) return true;
        return false;
    }
};