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;
    }
};