[[420388]]

給定一個(gè)只包括 '(' ，')' ，'{' ，'}' ，'[' ，']' 的字符串，判斷字符串是否有效。

有效字符串需滿(mǎn)足：

• 左括號(hào)必須用相同類(lèi)型的右括號(hào)閉合。
• 左括號(hào)必須以正確的順序閉合。

注意空字符串可被認(rèn)為是有效字符串。

示例 1:

輸入: "()" 
輸出: true 

示例 2:

輸入: "()[]{}" 
輸出: true 

示例 3:

輸入: "(]" 
輸出: false 

示例 4:

輸入: "(]" 
輸出: false 

示例 5:

輸入: "([)]" 
輸出: false 

解答：利用棧結(jié)構(gòu)

解題思路： 將字符串中的字符依次入棧，遍歷字符依次判斷：

• 首先判斷該元素是否是 { 、 ( 、 [ ，直接入棧
• 否則該字符為 } 、 ) 、 ] 中的一種，如果該字符串有效，則該元素應(yīng)該與棧頂匹配，例如棧中元素有 ({， 如果繼續(xù)遍歷到的元素為 ), 那么當(dāng)前元素序列為 ({) 是不可能有效的，所以此時(shí)與棧頂元素匹配失敗，則直接返回 false ，字符串無(wú)效

當(dāng)遍歷完成時(shí)，所有已匹配的字符都已匹配出棧，如果此時(shí)棧為空，則字符串有效，如果棧不為空，說(shuō)明字符串中還有未匹配的字符，字符串無(wú)效

畫(huà)圖幫助理解一下：

代碼實(shí)現(xiàn)：

const isValid = function(s) { 
    let map = { 
        '{': '}', 
        '(': ')', 
        '[': ']' 
    } 
    let stack = [] 
    for(let i = 0; i < s.length ; i++) { 
        if(map[s[i]]) { 
            stack.push(s[i]) 
        } else if(s[i] !== map[stack.pop()]){ 
            return false 
        } 
    } 
    return stack.length === 0 
}; 

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)