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: true
Example 2:
   Input: "()[]{}"
   Output: true
Example 3:
   Input: "(]"
   Output: false
Example 4:
   Input: "([)]"
   Output: false
Example 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

/**
 * @param {string} str
 * @return {boolean}
 */
const isValid = function(str) {
    const arr = [];
    const map = {
        "}": "{",
        ")": "(",
        "]": "[",
    }    
    for(let item of str){
       if(item === '{' || item === '(' || item === '['){
          arr.push(item);
       }else{
           if(arr.pop() !== map[item] ){
              return false;
           }
       }
    }
    return arr.length === 0;
};

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

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

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

if(arr.pop() !== map[item]){
    return false;
}

這邊在做「比較」的時候，是用 String 來做判斷的，如果改成用 Number 來判斷的話，速度就會快一點，所以我們要來小小修改一下剛剛的程式。

/**
 * @param {string} str
 * @return {boolean}
 */
const isValid = function(str) {
    const arr = [];
    const map = {
        "}": 1,
        ")": 2,
        "]": 3,
    }
    for(let item of str){
       if(item === '{'){
          arr.push(1);
       }else if(item === '('){
          arr.push(2);
       }else if(item === '['){
          arr.push(3);
       }else{
           if(arr.pop() !== map[item] ){
              return false;
           }
       }
    }
    return arr.length === 0;
};

整個速度就提升了不少~

好啦! 這次的解題就到這邊啦，接下來我會慢慢的分享一些關於其他題目的解題技巧，如果有更好的寫法請在下面留言給我知道，感謝。