面試官：你工作了3年了，這道算法題你都答不出來(lái)？
9月又是換工作的最佳時(shí)機(jī)。我幻想著只要換一份工作，就可以離開(kāi)這個(gè)“破碎的地方”，賺更多的錢(qián)，做最舒服的事情，但事與愿違。
最近，一名女學(xué)生正在換工作。面試前她準(zhǔn)備了很多問(wèn)題。我以為她很有信心，結(jié)果卻在算法上吃了大虧。
什么樣的算法題能讓面試官對(duì)一個(gè)女孩說(shuō)出這么狠的話：你工作了3年了，這道算法題你都解不出來(lái)？
有效括號(hào)
這是LeetCode上的一道算法題，旨在考察考生對(duì)“棧”數(shù)據(jù)結(jié)構(gòu)的熟悉程度。我們來(lái)看一下。
給定一個(gè)僅包含字符‘(‘、‘)’、‘{‘、‘}’、‘[‘和‘]’的字符串 s，確定輸入字符串是否有效。
如果滿足以下條件，輸入字符串有效：開(kāi)括號(hào)必須由相同類型的括號(hào)括起來(lái)。左括號(hào)必須按正確的順序關(guān)閉。
示例1：
Input: s = "()"
Output: true示例2：
Input: s = "()[]{}"
Output: true示例3：
Input: s = "(]"
Output: false示例4：
Input: s = "([)]"
Output: false實(shí)施例5：
Input: s = "{[]}"
Output: true限制條件：
- 1 <= s.length <= 104
- s 僅由括號(hào)‘()[]{}’組成
問(wèn)題信息
如果我們真的沒(méi)學(xué)過(guò)算法，也不知道那么多套路，那么通過(guò)問(wèn)題和例子來(lái)獲取盡可能多的信息是非常重要的。
那么，我們可以得到以下信息：
- 字符串 s 的長(zhǎng)度必須是偶數(shù)，不能是奇數(shù)（成對(duì)匹配）。
- 右括號(hào)前面必須有左括號(hào)。
方法一：暴力消除法
得到以上信息后，我想既然[]、{}、()是成對(duì)出現(xiàn)的，那我是不是可以一一消除呢？如果最后的結(jié)果是空字符串，那不是就說(shuō)明符合題意了嗎？
例如：
Input: s = "{[()]}"
Step 1: The pair of () can be eliminated, and the result s is left with {[]}
Step 2: The pair of [] can be eliminated, and the result s is left with {}
Step 3: The pair of {} can be eliminated, and the result s is left with '', so it returns true in line with the meaning of the question代碼：
const isValid = (s) => {
while (true) {
let len = s.length
// Replace the string with '' one by one according to the matching pair
s = s.replace('{}', '').replace('[]', '').replace('()', '')
// There are two cases where s.length will be equal to len
// 1. s is matched and becomes an empty string
// 2. s cannot continue to match, so its length is the same as the len at the beginning, for example ({], len is 3 at the beginning, and it is still 3 after matching, indicating that there is no need to continue matching, and the result is false
if (s.length === len) {
return len === 0
}
}
}暴力消除方式還是可以通過(guò)LeetCode的用例，但是性能差了一點(diǎn)，哈哈。
方法二：使用“棧”來(lái)解決
主題信息中的第二項(xiàng)強(qiáng)調(diào)對(duì)稱性。棧（后進(jìn)先出）和（推入和彈出）正好相反，形成明顯的對(duì)稱性。
例如
Input: abc
Output: cba“abc”和“cba”是對(duì)稱的，所以我們可以嘗試從堆棧的角度來(lái)解析：
Input: s = "{[()]}"
Step 1: read ch = {, which belongs to the left bracket, and put it into the stack. At this time, there is { in the stack.
Step 2: Read ch = [, which belongs to the left parenthesis, and push it into the stack. At this time, there are {[ in the stack.
Step 3: read ch = (, which belongs to the left parenthesis, and push it into the stack. At this time, there are {[( in the stack.
Step 4: Read ch = ), which belongs to the right parenthesis, try to read the top element of the stack (and ) just match, and pop ( out of the stack, at this time there are {[.
Step 5: Read ch = ], which belongs to the right parenthesis, try to read the top element of the stack [and ] just match, pop the [ out of the stack, at this time there are {.
Step 6: Read ch = }, which belongs to the right parenthesis, try to read the top element of the stack { and } exactly match, pop { out of the stack, at this time there is still '' in the stack.
Step 7: There is only '' left in the stack, s = "{[()]}" conforms to the valid bracket definition and returns true.代碼
const isValid = (s) => {
// The empty string character is valid
if (!s) {
return true
}
const leftToRight = {
'(': ')',
'[': ']',
'{': '}'
}
const stack = []
for (let i = 0, len = s.length; i < len; i++) {
const ch = s[i]
// Left parenthesis
if (leftToRight[ch]) {
stack.push(ch)
} else {
// start matching closing parenthesis
// 1. If there is no left parenthesis in the stack, directly false
// 2. There is data but the top element of the stack is not the current closing parenthesis
if (!stack.length || leftToRight[ stack.pop() ] !== ch) {
return false
}
}
}
// Finally check if the stack is empty
return !stack.length
}雖然暴力方案符合我們的常規(guī)思維，但是堆棧結(jié)構(gòu)方案會(huì)更加高效。
最后
在面試中，算法是否應(yīng)該成為評(píng)價(jià)候選人的重要指標(biāo)，我們不會(huì)抱怨，但近年來(lái)，幾乎每家公司都將算法納入了前端面試中。為了拿到自己喜歡的offer，復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)、刷題還是有必要的。
