欣迪

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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Constraints:

  • 1 <= s.length <= 104
  • s consists 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 個字是 ‘]’ ,這邊是一個封閉的括弧,必須驗證暫存陣列的最後一個結果是不是 ‘]’

如果是,則移除站存陣列的最後一個結果並繼續。

如果否,則驗證失敗。

就這樣將所有的字串逐字驗證完畢,如果是合法字串,最後的站存陣列的所有內容會剛好全部消除。

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。