Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Example 1:
Input: s = "()" Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]" Output: false
Constraints:
1 <= s.length <= 104sconsists of parentheses only'()[]{}'.
提示一
An interesting property about a valid parenthesis expression is that a sub-expression of a valid expression should also be a valid expression. (Not every sub-expression) e.g.
{ { } [ ] [ [ [ ] ] ] } is VALID expression
[ [ [ ] ] ] is VALID sub-expression
{ } [ ] is VALID sub-expression
Can we exploit this recursive structure somehow?
提示二
What if whenever we encounter a matching pair of parenthesis in the expression, we simply remove it from the expression? This would keep on shortening the expression. e.g.
{ { ( { } ) } }
|_|
{ { ( ) } }
|______|
{ { } }
|__________|
{ }
|________________|
VALID EXPRESSION!
提示三
The stack data structure can come in handy here in representing this recursive structure of the problem. We can’t really process this from the inside out because we don’t have an idea about the overall structure. But, the stack can help us process this recursively i.e. from outside to inwards.
var isValid = function(s) {
const map = {
'(' : ')',
'[' : ']',
'{' : '}'
}
const temp = []
for(let i = 0; i < s.length; i++) {
if (map[s[i]] !== undefined) {
temp.push(map[s[i]])
} else if(s[i] !== temp.pop()) {
return false
}
}
return temp.length === 0
};思路
這題很容易想得很複雜，甚至一開始還嘗試用標準表達式來解題。看了一下討論區，大家的解法之後才恍然大悟。
首先，有括弧的開頭，就必須有結尾。當開頭是兩個括弧，例如 ‘([’ 這時候的結尾必須是 ‘])’ 。 當括弧不斷增加結尾也必須隨之改變，也就是說，必須要有一個陣列，來記錄沒有被封閉的括弧。
假設第 1 個字是 ‘(‘ ，我們在暫存的陣列內容必須加入一個 ‘)’ ， 目前結果為 [‘)’]
假設第 2 個字是 ‘[‘ ，我們在暫存的陣列內容必須加入一個 ‘]’ ， 目前結果為 [‘)’, ‘]’]
假設第 3 個字是 ‘]’ ，這邊是一個封閉的括弧，必須驗證暫存陣列的最後一個結果是不是 ‘]’
如果是，則移除站存陣列的最後一個結果並繼續。
如果否，則驗證失敗。
就這樣將所有的字串逐字驗證完畢，如果是合法字串，最後的站存陣列的所有內容會剛好全部消除。
