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