JavaScript 的 Leetcode 演算之路(一)

演算法對一個工程師來說是一個非常重要的技能，先撇開在工作上面的實務影響不管，光在求職的過程中，就有許多面試需要考試，而考的內容八九不離十是演算法考題，所以對於一個厲害的工程師來說，演算法尤其的重要，偏偏我的數學跟資料結構沒有這麼厲害，所以我也需要花點苦工來好好的學習，接下來我就會透過leetcode這個演算法考題的網站，學習演算法，把我寫好的題目來分享給大家，可以一起討論。

這次要解的題目是這個 20. Valid Parentheses(Easy)

Given a string 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.Note that an empty string is also considered valid.Example 1:
   Input: "()"
   Output: trueExample 2:
   Input: "()[]{}"
   Output: trueExample 3:
   Input: "(]"
   Output: falseExample 4:
   Input: "([)]"
   Output: falseExample 5:
   Input: "{[]}"
   Output: true

簡單來講就是給你一串都是括號所組成的字串，你要判斷小括號、中括號、大括號是不是成對的，只要是字串內的括號都是成對的就回傳 true，如果有一個不是成對的就回傳 false，看看題目提供的 example 真是簡單明瞭XD

以下是 leetcode 幫我們準備好空白的 function

/**
 * @param {string} str
 * @return {boolean}
 */
const isValid = function(str) {};

接下來讓我們來思考解題的思路

1. 首先需要對字串去跑一個迴圈，遍歷每個字元出來。
2. 在來我們需要先比對 ” { “、” [ “、” ( ” 這幾個開頭的括號。
3. 把開頭括號先存進一個暫存的 Array 裡面。
4. 當遇到 ” } “、” ] “、” ) ” 結尾括號的時候就先去把剛剛暫存的 Array 最後的那個括號取出來然後比較。
5. 比較一錯就直接回傳 false，如果對了就繼續比較下去。
6. 最後暫存 Array 長度為零的時候，就代表全部比較都成功，回傳 true。

比照上面的思考邏輯，以下是我的完成 code

（此區域有程式碼無法顯示，請點按下方連結回到原文查看，不好意思。）

https://gist.github.com/MikeCheng1208/bfaf28b96db0fd7b72618d1e4400c4d7#file-generate-parentheses-js

這邊我用了一個 map object 去記錄括號的對應，當遇到結尾括號的時候就可以透過 Array.pop() 去比對這個 map object。

這時候問題來了，還能不能再優化 ?

魔鬼藏在細節裡，我們看這邊

if(arr.pop() !== map){

    return false;

Tags:
FireLab時效內容現代化更新