LeetCode Problem: Valid Parentheses 詳解

Description

給定一個只包含'('、'['、'{'、')'、']'、'}'的字串 string s，判定此字串是否為合法。合法的條件如下：

開字符(open brackets: '('、'['、'{')必須與關字符(closed brackets: ')'、']'、'}')搭配
開字符必須以正確的順序被關閉 (當開字符遇到對應的關字符，稱為被關閉)

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "([)]"
Output: false

Example 4:

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

Solution

此題目為Leetcode easy的難度，解法較單純，可以利用Stack的資料結構解決，因為在Stack裡面最先遇到的開字符必定會與最後遇到的關字符配對，最後遇到的開字符必定會與最先遇到的關字符配對(見上面Eamples)，因此開字符符合first in last out的原則，以Stack實踐最為適合，我們以下面幾個範例說明。假設給定的字串為 "({})[]" ，我們可以從頭開始讀取，若是遇見開字符則存入Stack當中，當我們遇見關字符時，則將最後加入Stack的開字符取出並且配對，若配對成功則繼續讀取下個字符，否則直接回傳 false 。

另外需要注意的是，本題會出現 "]" 的測資，因為完全沒有開字符，因此遇到關字符 "]" 要從Stack取出開字符時會出現 Error!，因此每次取出開字符前需要確保 Stack 的 size 不為0，若 Stack 為空則代表沒有對應的開字符，直接回傳 false。最後，我們發現所有關字符與開字符照順序配對成功後，必須確保 Stack 裡面為空才回傳 true，為了避免以下情形。

完整程式算法如下(in C++)

class Solution {
public:
    bool isValid(string s) {
        vector<char> record;
        for (auto &c: s)
        {
            if (c == '(' || c == '{' || c == '[')
            {
                record.push_back(c);
            }
            else
            {
                if (record.size() == 0) return false;
                else if (c == ')' && record.back() != '(') return false;
                else if (c == '}' && record.back() != '{') return false;
                else if (c == ']' && record.back() != '[') return false;

                record.pop_back();
            }
        }

        return record.size() > 0 ? false : true;
    }
};