現(xiàn)實總是殘酷的，最近有個學(xué)妹在換工作，面試前什么手寫Priomise、vue雙向綁定原理,webpack優(yōu)化方式,準(zhǔn)備了一大堆，本以為成竹在胸，結(jié)果卻在算法上吃了大虧，心儀的offer沒有拿到，一度懷疑人生。到底是什么算法題能讓面試官對妹子說出你都工作3年了，這個算法題都不會？這樣的狠話？

有效的括號問題

這是一道leetcode上的原題，本意是在考察候選人對棧數(shù)據(jù)結(jié)構(gòu)的掌握。來看看題目

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。有效字符串需滿足：

左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。

示例：

示例 1：
輸入：s = "()"
輸出：true

示例 2：
輸入：s = "()[]{}"
輸出：true

示例 3：
輸入：s = "(]"
輸出：false

示例 4：
輸入：s = "([)]"
輸出：false

示例 5：
輸入：s = "{[]}"
輸出：true

解題信息

如果咱們確實沒有刷過算法，不知道那么多套路，通過題目和示例盡可能的獲取到更多的信息就很重要了。

根據(jù)題目推斷出：

字符串s的長度一定是偶數(shù)，不可能是奇數(shù)(一對對匹配)。
右括號前面一定跟著左括號，才符合匹配條件，具備對稱性。
右括號前面如果不是左括號，一定不是有效的括號。

暴力消除法

得到了以上這些信息后，胖頭魚想既然是[]、{}、()成對的出現(xiàn)，我能不能把他們都挨個消除掉，如果最后結(jié)果是空字符串，那不就意味著符合題意了嗎？

舉個例子：

輸入：s = "{[()]}"

第一步：可以消除()這一對，結(jié)果s還剩{[]}

第二步: 可以消除[]這一對，結(jié)果s還剩{}

第三步: 可以消除{}這一對，結(jié)果s還剩'' 所以符合題意返回true

代碼實現(xiàn)：

const isValid = (s) => {
  while (true) {
    let len = s.length
    // 將字符串按照匹配對，挨個替換為''
    s = s.replace('{}', '').replace('[]', '').replace('()', '')
    // 有兩種情況s.length會等于len
    // 1. s匹配完了，變成了空字符串
    // 2. s無法繼續(xù)匹配，導(dǎo)致其長度和一開始的len一樣，比如({],一開始len是3，匹配完還是3，說明不用繼續(xù)匹配了，結(jié)果就是false
    if (s.length === len) {
      return len === 0
    }
  }
}

暴力消除法最終還是可以通過leetcode的用例，就是性能差了點，哈哈

棧解題法

解題信息中的第2條強調(diào)對稱性，而棧（后入先出）入棧和出棧恰好是反著來，形成了鮮明的對稱性。

入棧：abc，出棧：cba

abc
cba

所以可以試試從棧的角度來解析：

輸入：s = "{[()]}"

第一步：讀取ch = {，屬于左括號，入棧，此時棧內(nèi)有{
第二步：讀取ch = [，屬于左括號，入棧，此時棧內(nèi)有{[
第三步：讀取ch = (，屬于左括號，入棧，此時棧內(nèi)有{[(
第四步：讀取ch = )，屬于右括號，嘗試讀取棧頂元素(和)正好匹配，將(出棧，此時棧內(nèi)還剩{[
第五步：讀取ch = ]，屬于右括號，嘗試讀取棧頂元素[和]正好匹配，將[出棧，此時棧內(nèi)還剩{
第六步：讀取ch = }，屬于右括號，嘗試讀取棧頂元素{和}正好匹配，將{出棧，此時棧內(nèi)還剩''
第七步：棧內(nèi)只能''，s = "{[()]}"符合有效的括號定義，返回true

代碼實現(xiàn)：

const isValid = (s) => {
  // 空字符串符合條件
  if (!s) {
    return true
  }

  const leftToRight = {
    '(': ')',
    '[': ']',
    '{': '}'
  }
  const stack = []

  for (let i = 0, len = s.length; i < len; i++) {
    const ch = s[i]
    // 左括號
    if (leftToRight[ch]) {
      stack.push(ch)
    } else {
      // 右括號開始匹配
      // 1. 如果棧內(nèi)沒有左括號，直接false
      // 2. 有數(shù)據(jù)但是棧頂元素不是當(dāng)前的右括號
      if (!stack.length || leftToRight[ stack.pop() ] !== ch) {
        return false
      }
    }
  }

  // 最后檢查棧內(nèi)還有沒有元素，有說明還有未匹配則不符合
  return !stack.length
}

暴力解法雖然符合我們?nèi)粘５乃季S，但是果然還是棧結(jié)構(gòu)解法好了不少。