【Leetcode 做題學演算法周刊】第二期

  • 2019 年 11 月 5 日
  • 筆記

首發於微信公眾號《前端成長記》，寫於 2019.11.05

背景

本文記錄刷題過程中的整個思考過程，以供參考。主要內容涵蓋：

  • 題目分析設想
  • 編寫程式碼驗證
  • 查閱他人解法
  • 思考總結

目錄

Easy

20.有效的括弧

題目地址

題目描述

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

有效字元串需滿足：

  1. 左括弧必須用相同類型的右括弧閉合。
  2. 左括弧必須以正確的順序閉合。

注意空字元串可被認為是有效字元串。

示例：

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

題目分析設想

這道題從題面來看，仍然需要對字元串做遍歷處理，找到相互匹配的括弧，剔除後繼續做處理即可。所以這道題我的解題想法是：

  • 使用棧來記錄，匹配的一對就出棧，最後判斷棧是否為空

有幾點需要注意下，可以減少一些計算量：

  1. 題面說明了字元串只含有三種括弧，所以長度為奇數，一定無效
  2. 只要有一對不符合，則可判定一定無效
  3. 堆棧長度超過字元串長度一半，則一定無效
  4. 先找到右括弧則一定無效

編寫程式碼驗證

Ⅰ.記錄棧

程式碼：

/**   * @param {string} s   * @return {boolean}   */  var isValid = function(s) {      if (s === '') return true;      if (s.length % 2) return false;      // hash 表做好索引      const hash = {          '(': ')',          '[': ']',          '{': '}'      }      let arr = []      for (let i = 0; i < s.length; i++) {          if (!hash[s.charAt(i)]) { // 推入的是右括弧              if (!arr.length || hash[arr[arr.length - 1]] !== s.charAt(i)) {                  return false              } else {                  arr.pop()              }          } else {              if (arr.length >= s / 2) {   // 長度超過一半                  return false              }              arr.push(s.charAt(i))          }      }      return !arr.length  };

結果：

  • 76/76 cases passed (64 ms)
  • Your runtime beats 90.67 % of javascript submissions
  • Your memory usage beats 64.59 % of javascript submissions (33.8 MB)
  • 時間複雜度： O(n)

查閱他人解法

發現一個很暴力的解法，雖然效率不高，但是思路清奇。我們來看看實現：

Ⅰ.暴力正則

程式碼：

/**   * @param {string} s   * @return {boolean}   */  var isValid = function(s) {      if (s === '') return true;      if (s.length % 2) return false;        while(s.length) {          const s_ = s          s = s.replace('()','').replace('[]','').replace('{}','')          if (s === s_) return false;      }      return true;  };

結果：

  • 76/76 cases passed (104 ms)
  • Your runtime beats 14.95 % of javascript submissions
  • Your memory usage beats 19.75 % of javascript submissions (35.7 MB)
  • 時間複雜度： O(n)

思考總結

就這題而言，我還是更傾向於增加一個輔助棧來做記錄。因為一旦去掉只包含括弧的限制，那麼正則將無法解答。

21.合併兩個有序鏈表

題目地址

題目描述

將兩個有序鏈表合併為一個新的有序鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

示例：

輸入：1->2->4, 1->3->4  輸出：1->1->2->3->4->4

題目分析設想

這道題從題面上就說明了這是一道鏈表相關問題，要進行鏈表合併，無非是修改鏈表指針指向，或者是鏈表拼接。所以，這道題我有兩種思路的解法：

  • 修改指針，不斷取出某一條鏈表中的數，插入到另外一條鏈表
  • 鏈表拼接，遞歸比較哪條鏈表的元素更小，就截取拼接到另一條

兩種方式的區別很明顯，修改指針的方式需要存儲和不斷修改指針指向，拼接的方式直接做鏈表拼接。

當然這裡也有一些特殊值需要考慮進來。

編寫程式碼驗證

Ⅰ.修改指針

程式碼：

/**   * @param {ListNode} l1   * @param {ListNode} l2   * @return {ListNode}   */  var mergeTwoLists = function(l1, l2) {      if (l1 === null) return l2      if (l2 === null) return l1      // 結果鏈表      let l = new ListNode(0)      // 不斷更新的當前結點指針，對象賦值為傳址，所以下面改指針指向即可      let cursor = l      // 會有一個先遍歷完，變成 null      while(l1 !== null && l2 !== null) {          if (l1.val <= l2.val) { // 哪個小，指針就指向哪              cursor.next = l1              l1 = l1.next          } else {              cursor.next = l2              l2 = l2.next          }          // 可以理解為 l.next.next.next ...          cursor = cursor.next      }      // 有一個為空則可以直接拼接      cursor.next = l1 === null ? l2 : l1      return l.next  };

結果：

  • 208/208 cases passed (60 ms)
  • Your runtime beats 99.51 % of javascript submissions
  • Your memory usage beats 51.04 % of javascript submissions (35.4 MB)
  • 時間複雜度 O(m + n) ，分別代表兩個鏈表長度

Ⅱ.鏈表拼接

程式碼：

/**   * @param {ListNode} l1   * @param {ListNode} l2   * @return {ListNode}   */  var mergeTwoLists = function(l1, l2) {      if (l1 === null) return l2      if (l2 === null) return l1      if (l1.val < l2.val) {          l1.next = mergeTwoLists(l1.next, l2)          return l1   // 這個是合併後的了      } else {          l2.next = mergeTwoLists(l1, l2.next)          return l2   // 這個是合併後的了      }  };

結果：

  • 208/208 cases passed (68 ms)
  • Your runtime beats 96.41 % of javascript submissions
  • Your memory usage beats 51.04 % of javascript submissions (35.4 MB)
  • 時間複雜度 O(m + n) ，分別代表兩個鏈表長度

查閱他人解法

思路基本上都是這兩種，未發現方向不同的解法。

無非是有些解法額外開闢了新的鏈表來記錄，或者一些細節上的差異。

思考總結

這裡的鏈表拼接解法，有沒有發現跟 上一期 14題中的分治思路是一樣的？對，實際上這個也是分治思路的一個應用。

26.刪除排序數組中的重複項

題目地址

題目描述

給定一個排序數組，你需要在原地刪除重複出現的元素，使得每個元素只出現一次，返回移除後數組的新長度。

不要使用額外的數組空間，你必須在原地修改輸入數組並在使用 O(1) 額外空間的條件下完成。

示例：

給定數組 nums = [1,1,2],    函數應該返回新的長度 2, 並且原數組 nums 的前兩個元素被修改為 1, 2。    你不需要考慮數組中超出新長度後面的元素。    給定 nums = [0,0,1,1,1,2,2,3,3,4],    函數應該返回新的長度 5, 並且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。    你不需要考慮數組中超出新長度後面的元素。

說明:

為什麼返回數值是整數，但輸出的答案是數組呢?

請注意，輸入數組是以「引用」方式傳遞的，這意味著在函數里修改輸入數組對於調用者是可見的。

你可以想像內部操作如下:

// nums 是以「引用」方式傳遞的。也就是說，不對實參做任何拷貝  int len = removeDuplicates(nums);    // 在函數里修改輸入數組對於調用者是可見的。  // 根據你的函數返回的長度, 它會列印出數組中該長度範圍內的所有元素。  for (int i = 0; i < len; i++) {      print(nums[i]);  }

題目分析設想

如果是單純的數組去重，那有很多種方法可以做。所以題目也加了限制條件，總結一下比較重要的幾點：

  • 不要使用額外的數組空間，空間複雜度為 O(1)
  • 原地刪除重複元素
  • 不需要考慮超過新長度後面的元素

這意味著不允許使用新的數組來解題，也就是對原數組進行操作。最後一點注意點可以看出，數組項的拷貝複製是一個方向，第二點可以看出數組刪除是一個方向。刪除元素的話就不會超過，所以不需要考慮兩者結合。所以這題我分兩個方向來解：

  • 拷貝數組元素
  • 刪除數組元素

編寫程式碼驗證

Ⅰ.拷貝數組元素

程式碼：

/**   * @param {number[]} nums   * @return {number}   */  var removeDuplicates = function(nums) {      if (nums.length === 0) return 0;      var len = 1      for(let i = 1; i < nums.length; i++) {          if(nums[i] !== nums[i - 1]) { // 後一項不等於前一項              nums[len++] = nums[i] // 拷貝數組元素          }      }      return len  };

結果：

  • 161/161 cases passed (68 ms)
  • Your runtime beats 99.81 % of javascript submissions
  • Your memory usage beats 77.54 % of javascript submissions (36.6 MB)
  • 時間複雜度 O(n)

Ⅱ.刪除數組元素

程式碼：

/**   * @param {number[]} nums   * @return {number}   */  var removeDuplicates = function(nums) {      if (nums.length === 0) return 0;      for(let i = 1; i < nums.length;) {          if(nums[i] === nums[i - 1]) { // 後一項等於前一項              nums.splice(i, 1)          } else {              i++          }      }      return nums.length  };

結果：

  • 161/161 cases passed (96 ms)
  • Your runtime beats 75.93 % of javascript submissions
  • Your memory usage beats 30.85 % of javascript submissions (37.3 MB)
  • 時間複雜度 O(n)

查閱他人解法

這裡看見一種很巧妙的解法，雙指針法。相當於一個用於計數，一個用於掃描。

Ⅰ.雙指針法

程式碼：

/**   * @param {number[]} nums   * @return {number}   */  var removeDuplicates = function(nums) {      if (nums.length === 0) return 0;        let i = 0;      for(let j = 1; j < nums.length; j++) {          if (nums[j] !== nums[i]) {              nums[++i] = nums[j]          }      }      return i + 1  // 下標 +1 為數組長度  };

結果：

  • 161/161 cases passed (68 ms)
  • Your runtime beats 99.81 % of javascript submissions
  • Your memory usage beats 84.03 % of javascript submissions (36.5 MB)
  • 時間複雜度 O(n)

思考總結

就三種解法而言，刪除數組元素會頻繁修改數組，不建議使用。雙指針法和拷貝數組元素程式碼邏輯相似，但是思路上是截然不同的。

27.移除元素

題目地址

題目描述

給定一個數組 nums 和一個值 val，你需要原地移除所有數值等於 val 的元素，返回移除後數組的新長度。

不要使用額外的數組空間，你必須在原地修改輸入數組並在使用 O(1) 額外空間的條件下完成。

元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。

示例：

給定 nums = [3,2,2,3], val = 3,    函數應該返回新的長度 2, 並且 nums 中的前兩個元素均為 2。    你不需要考慮數組中超出新長度後面的元素。    給定 nums = [0,1,2,2,3,0,4,2], val = 2,    函數應該返回新的長度 5, 並且 nums 中的前五個元素為 0, 1, 3, 0, 4。    注意這五個元素可為任意順序。    你不需要考慮數組中超出新長度後面的元素。

說明:

為什麼返回數值是整數，但輸出的答案是數組呢?

請注意，輸入數組是以「引用」方式傳遞的，這意味著在函數里修改輸入數組對於調用者是可見的。

你可以想像內部操作如下:

// nums 是以「引用」方式傳遞的。也就是說，不對實參作任何拷貝  int len = removeElement(nums, val);    // 在函數里修改輸入數組對於調用者是可見的。  // 根據你的函數返回的長度, 它會列印出數組中該長度範圍內的所有元素。  for (int i = 0; i < len; i++) {      print(nums[i]);  }

題目分析設想

這題跟上一題非常相似，所以我們可以沿用上題的方向來解這道題：

  • 刪除數組元素
  • 雙指針法

編寫程式碼驗證

Ⅰ.刪除數組元素

程式碼：

/**   * @param {number[]} nums   * @param {number} val   * @return {number}   */  var removeElement = function(nums, val) {      if (nums.length === 0) return 0;        for(let i = 0; i < nums.length;) {          if (nums[i] === val) {              nums.splice(i, 1)          } else {              i++          }      }  };

結果：

  • 113/113 cases passed (64 ms)
  • Your runtime beats 89.43 % of javascript submissions
  • Your memory usage beats 47.42 % of javascript submissions (33.7 MB)
  • 時間複雜度 O(n)

Ⅱ.雙指針法

程式碼：

/**   * @param {number[]} nums   * @param {number} val   * @return {number}   */  var removeElement = function(nums, val) {      if (nums.length === 0) return 0;        let i = 0      for(let j = 0; j < nums.length; j++) {          if (nums[j] !== val) {              nums[i++] = nums[j]          }      }      return i  };

結果：

  • 113/113 cases passed (60 ms)
  • Your runtime beats 95.11 % of javascript submissions
  • Your memory usage beats 98.18 % of javascript submissions (33.3 MB)
  • 時間複雜度 O(n)

查閱他人解法

看到兩個略有差異的方法：

  • 單指針法，使用 const of 替換一次遍歷，只是寫法區別，沒有本質提升
  • 交換移除，相同時候與最後一項交換，同時數組長度減1

Ⅰ.單指針法

程式碼：

/**   * @param {number[]} nums   * @param {number} val   * @return {number}   */  var removeElement = function(nums, val) {      if (nums.length === 0) return 0;        let i = 0;      for(const num of nums) {          if(num !== val) {              nums[i++] = num;          }      }      return i;  };

結果：

  • 113/113 cases passed (68 ms)
  • Your runtime beats 80.29 % of javascript submissions
  • Your memory usage beats 43.35 % of javascript submissions (33.7 MB)
  • 時間複雜度 O(n)

Ⅱ.交換移除

程式碼：

/**   * @param {number[]} nums   * @param {number} val   * @return {number}   */  var removeElement = function(nums, val) {      if (nums.length === 0) return 0;        let i = nums.length;      for(let j = 0; j < i;) {          if (nums[j] === val) {              nums[j] = nums[--i]          } else {              j++          }      }        return i;  };

結果：

  • 113/113 cases passed (68 ms)
  • Your runtime beats 80.29 % of javascript submissions
  • Your memory usage beats 44.53 % of javascript submissions (33.7 MB)
  • 時間複雜度 O(n)

思考總結

這裡開拓下思路：如果要移除的是多項，那麼還是使用指針法做處理合適；如果是移除單項，那麼使用交互移除法其實遍歷次數最少。

28.實現strStr

題目地址

題目描述

實現 strStr() 函數。

給定一個 haystack 字元串和一個 needle 字元串，在 haystack 字元串中找出 needle 字元串出現的第一個位置 (從0開始)。如果不存在，則返回 -1。

示例：

輸入: haystack = "hello", needle = "ll"  輸出: 2    輸入: haystack = "aaaaa", needle = "bba"  輸出: -1

說明:

當 needle 是空字元串時，我們應當返回什麼值呢？這是一個在面試中很好的問題。

對於本題而言，當 needle 是空字元串時我們應當返回 0 。這與 C 語言的 strstr() 以及 Java 的 indexOf() 定義相符。

題目分析設想

這道題很明顯是一道字元串搜索的題目，估計是在考察演算法，但是受限知識面，所以我就先以現有方式實現作答，再來學習演算法了。

  • IndexOf 這個是原生方法，考察這個就沒有意義了，所以不做詳細論述
  • 遍歷匹配，相當於自己實現一個 IndexOf

編寫程式碼驗證

Ⅰ.遍歷匹配

程式碼：

/**   * @param {string} haystack   * @param {string} needle   * @return {number}   */  var strStr = function(haystack, needle) {      if (needle === '') return 0      if (needle.length > haystack.length) return -1      if (needle.length === haystack.length && needle !== haystack) return -1      for(let i = 0; i < haystack.length; i++) {          if (i + needle.length > haystack.length) {              return -1          } else {              const str = haystack.substr(i, needle.length)              if (str === needle) {                  return i              }          }      }      return -1  };

結果：

  • 74/74 cases passed (64 ms)
  • Your runtime beats 90.58 % of javascript submissions
  • Your memory usage beats 44.22 % of javascript submissions (33.9 MB)
  • 時間複雜度 O(n)

查閱他人解法

首先查閱《演算法導論》，看到字元串匹配有以下四種：

  • 樸素字元串匹配演算法
  • Rabin-Karp 演算法
  • 利用有限自動機進行字元串匹配
  • KMP 演算法

然後再看題解，大概還找到以下三種演算法：

  • BM 演算法
  • Horspool 演算法
  • Sunday 演算法

Ⅰ.樸素字元串匹配演算法

演算法說明：

通過一個循環找到所有有效便宜，該循環對 n-m+1 個可能的 s 值進行檢測，看能否滿足條件 P[1..m] = T[s+1...s+m]。其中 n 是字元串長度， ‘m’ 是匹配字元串長度。

程式碼：

/**   * @param {string} haystack   * @param {string} needle   * @return {number}   */  var strStr = function(haystack, needle) {      if (needle === '') return 0      if (needle.length > haystack.length) return -1      if (needle.length === haystack.length && needle !== haystack) return -1        let i = 0;      let j = 0;      while(j < needle.length && i < haystack.length) {          if(haystack[i] === needle[j]) { // 同位相等，繼續判斷下一位              i++;              j++;          } else {              i = i - j + 1; // i 偏移              j = 0; // j 重置                if (i + needle.length > haystack.length) { // 我增加的優化點，減少一些運算                  return -1              }          }      }      if (j >= needle.length) { // 子串比完了，此時 j 應該等於 needle.length          return i - needle.length;      } else {          return -1      }  };

結果：

  • 74/74 cases passed (56 ms)
  • Your runtime beats 98.45 % of javascript submissions
  • Your memory usage beats 30.12 % of javascript submissions (34.8 MB)
  • 時間複雜度 O(m*n)

Ⅱ.Rabin-Karp 演算法

演算法說明：

進行哈希運算，將字元串轉成對應的哈希值進行比對，類似16進位。這裡題目是字元串，我就用 ASCII 值來表示每個字元的哈希值，那麼就可以計算出模式串的哈希值，再進行滾動比較。

每次滾動只需要做固定的 -*+ 三個操作，即可得出滾動串的哈希值了。

比如計算 bbc ,哈希值為 hash = (b.charCodeAt() * 128 ^ 2 + b.charCodeAt() * 128 + c.charCodeAt())，如果要計算後新值 bca 則為 (hash - b.charCodeAt() * 128 ^ 2) * 128 + c.charCodeAt()。

程式碼：

/**   * @param {string} haystack   * @param {string} needle   * @return {number}   */  var strStr = function(haystack, needle) {      if (needle === '') return 0      if (needle.length > haystack.length) return -1      if (needle.length === haystack.length && needle !== haystack) return -1        let searchHash = 0 // 搜索字元串的hash值      let startHash = 0 // 字元串起始的hash值        for(let i = 0; i < needle.length; i++) {          searchHash += needle.charCodeAt(i) * Math.pow(2, needle.length - i - 1)          startHash += haystack.charCodeAt(i) * Math.pow(2, needle.length - i - 1)      }        if (startHash === searchHash)  return 0        for(let j = 1; j < haystack.length - needle.length + 1; j++) {          startHash = (startHash - haystack.charCodeAt(j - 1) * Math.pow(2, needle.length - 1)) * 2 + haystack.charCodeAt(j + needle.length - 1)          if (startHash === searchHash) {              return j          }      }      return -1  };

結果：

  • 74/74 cases passed (68 ms)
  • Your runtime beats 81.31 % of javascript submissions
  • Your memory usage beats 16.86 % of javascript submissions (35.4 MB)
  • 時間複雜度 O(m*n)

注意：這裡可能會存在溢出的情況，所以不是所有情況都適用。

Ⅲ.利用有限自動機進行字元串匹配

演算法說明：

通過對文本字元串 T 進行掃描，找出模式 P 的所有出現位置。它們只對每個文本字元檢查一次，並且檢查每個文本字元時所用的時間為常數。一句話概括：字元輸入引起狀態機狀態變更，通過狀態轉換圖得到預期結果。

這裡主要的核心點是判斷每次輸入，找到最長的後綴匹配，如果最長時的長度等於查找字元串長度，那就一定包含該查找字元串。

程式碼：

/**   * @param {string} haystack   * @param {string} needle   * @return {number}   */  var strStr = function(haystack, needle) {      if (needle === '') return 0      if (needle.length > haystack.length) return -1      if (needle.length === haystack.length && needle !== haystack) return -1        // 查找最大匹配後綴長度      function findSuffix (Pq) {          let suffixLen = 0          let k = 0          while(k < Pq.length && k < needle.length) {              let i = 0;              for(i = 0; i <= k; i++) {                  // 找needle中的多少項為當前狀態對應字元串的匹配項                  if (Pq.charAt(Pq.length - 1 - k + i) !== needle.charAt(i)) {                      break;                  }              }                // 所有項都匹配，即找到了後綴              if (i - 1 == k) {                  suffixLen = k+1;               }              k++          }          return suffixLen      }        // 獲取所有輸入的字符集，比如 'abbc' 和 'cd' 合集為 ['a','b','c','d']      const setArr = Array.from(new Set(haystack + needle)) // 用戶輸入的可選項        // 建立狀態機      const hash = {}      for(let q = 0; q < haystack.length; q++) {          for(let k = 0; k < setArr.length; k++) {              const char = haystack.substring(0, q) + setArr[k] // 下個狀態的字元              const nextState = findSuffix(char)              // 求例如 0.a 0.b 0.c 的值              if (!hash[q]) {                  hash[q] = {}              }              hash[q][char] = nextState          }      }        // 根據狀態機求解      let matchStr = ''      for(let n = 0; n < haystack.length; n++) {          const map = hash[n]          matchStr += haystack[n]          const nextState = map[matchStr]            if (nextState === needle.length) {              return n - nextState + 1          }      }      return -1  };

結果：

  • 74/74 cases passed (84 ms)
  • Your runtime beats 35.05 % of javascript submissions
  • Your memory usage beats 5.05 % of javascript submissions (39.8 MB)
  • 時間複雜度 O(n)

Ⅳ.KMP 演算法

演算法說明：

可以理解為在狀態機的基礎上，使用了一個前綴函數來進行狀態判斷。本質上也是前綴後綴的思想。

程式碼：

// @lc code=start  /**   * @param {string} haystack   * @param {string} needle   * @return {number}   */  var strStr = function(haystack, needle) {      if (needle === '') return 0      if (needle.length > haystack.length) return -1      if (needle.length === haystack.length && needle !== haystack) return -1        // 生成匹配串各個位置下下的最長公共前後綴長度哈希表      function getHash () {          let i = 0 // arr[i] 表示 i 前面的字元串的最長公共前後綴長度          let j = 1          let hash = {              0: 0          }          while (j < needle.length) {              if (needle.charAt(i) === needle.charAt(j)) { // 相等直接 i j 都後移                  hash[j++] = ++i              } else if (i === 0) {   // i 為起點且兩者不相等，那麼一定為0                  hash[j] = 0                  j++              } else {                  // 這裡解釋一下： 因為i前面的字元串與j前面的字元串擁有相同的最長公共前後綴，也就是說i前面字元串的最長公共後綴與j前面字元串的最長公共前綴相同，所以i只需回到i前面字元串最長公共前綴的後一位開始比較                  i = hash[i - 1]              }          }          return hash      }        const hash = getHash()      let i = 0 // 母串中的位置      let j = 0 // 子串中的位置      while(i < haystack.length && j < needle.length) {          if (haystack.charAt(i) === needle.charAt(j)) {  // 兩個匹配，同時後移              i++              j++          } else if (j === 0) { // 兩個不匹配，並且j在起點，則母串後移              i++          } else {              j = hash[j - 1]          }      }      if (j === needle.length) {  // 循環完了，說明匹配到了          return i - j      } else {          return -1      }  };

結果：

  • 74/74 cases passed (60 ms)
  • Your runtime beats 94.74 % of javascript submissions
  • Your memory usage beats 23.73 % of javascript submissions (35.1 MB)
  • 時間複雜度 O(n)

Ⅴ.BM 演算法

演算法說明：

基於後綴匹配，匹配從後開始，但移動還是從前開始，只是定義了兩個規則：壞字元規則和好後綴規則。

通俗來講就是先驗證是否為壞字元，然後判斷是否在搜索詞中進行對應的偏移進行下一步驗證。如果匹配的話就從後往前校驗，如果仍然匹配，就為好後綴。核心思想是每次位移都在壞字元和好後綴規則中取較大值，由於兩個規則都只與匹配項相關，所以可以提前生成規則表。

程式碼：

/**   * @param {string} haystack   * @param {string} needle   * @return {number}   */  var strStr = function(haystack, needle) {      if (needle === '') return 0      if (needle.length > haystack.length) return -1      if (needle.length === haystack.length && needle !== haystack) return -1        function makeBadChar (needle) {          let hash = {}          for(let i = 0; i < 256; i++) { // ascii 字元長度              hash[String.fromCharCode(i)] = -1 // 初始化為-1          }          for(let i = 0; i < needle.length; i++) {              hash[needle.charAt(i)] = i  // 最後出現該字元的位置          }          return hash      }        function makeGoodSuffix (needle) {          let hashSuffix = {}          let hashPrefix = {}          for(let i = 0; i < needle.length; i++) {              hashSuffix[i] = -1              hashPrefix[i] = false          }          for(let i = 0; i < needle.length - 1; i++) { // needle[0, i]              let j = i              k = 0 // 公共後綴子串長度，尾部取k個出來進行比較              while(j >= 0 && needle.charAt(j) === needle.charAt(needle.length - 1 - k)) { // needle[0,needle.length - 1]                  --j                  ++k                  hashSuffix[k] = j + 1 // 起始下標              }                if (j === -1) { // 說明全部匹配，意味著此時公共後綴子串也是模式的前綴子串                  hashPrefix[k] = true              }          }          return { hashSuffix, hashPrefix }      }        function moveGoodSuffix (j, needle) {          let k = needle.length - 1 - j          let suffixes = makeGoodSuffix(needle).hashSuffix          let prefixes = makeGoodSuffix(needle).hashPrefix          if (suffixes[k] !== -1) { // 找到了跟好後綴一樣的子串，獲取下標              return j - suffixes[k] + 1          }          for(let r = j + 2; r < needle.length; ++r) {              if (prefixes[needle.length - r]) { // needle.length 是好後綴子串長度                  return r // 對齊前綴到好後綴              }          }          return needle.length // 全部匹配，直接移動字元串長度      }        let badchar = makeBadChar(needle)      let i = 0;      while(i < haystack.length - needle.length + 1) {          let j          for(j = needle.length - 1; j >= 0; --j) {              if (haystack.charAt(i + j) != needle[j]) {                  break; // 壞字元，下標為j              }          }          if (j < 0) { // 匹配成功              return i // 第一個匹配字元的位置          }          let moveLen1 = j - badchar[haystack.charAt(i + j)]          let moveLen2 = 0          if (j < needle.length -1) { // 如果有好後綴              moveLen2 = moveGoodSuffix(j, needle)          }          i = i + Math.max(moveLen1, moveLen2)      }        return -1  };

結果：

  • 74/74 cases passed (72 ms)
  • Your runtime beats 69.29 % of javascript submissions
  • Your memory usage beats 5.05 % of javascript submissions (37 MB)
  • 時間複雜度 O(n)

Ⅵ.Horspool 演算法

演算法說明：

將主串中匹配窗口的最後一個字元跟模式串中的最後一個字元比較。如果相等，繼續從後向前對主串和模式串進行比較，直到完全相等或者在某個字元處不匹配為止。如果不匹配，則根據主串匹配窗口中的最後一個字元在模式串中的下一個出現位置將窗口向右移動。

程式碼：

/**   * @param {string} haystack   * @param {string} needle   * @return {number}   */  var strStr = function(haystack, needle) {      if (needle === '') return 0      if (needle.length > haystack.length) return -1      if (needle.length === haystack.length && needle !== haystack) return -1        let hash = {}      for(let i = 0; i < 256; i++) {          hash[i] = needle.length // 默認初始化為最大偏移量，也就是匹配串長度      }      for(let i = 0; i < needle.length - 1; i++) {          hash[needle.charCodeAt(i)] = needle.length - 1 - i // 每個字元距離右側的距離      }        let pos = 0        while(pos < (haystack.length - needle.length + 1)) {          let j = needle.length - 1 // 從右往左          while(j >= 0 && haystack.charAt(pos + j) === needle.charAt(j)) {              j--          }          if (j < 0) { // 全部匹配              return pos          } else { // 不匹配              pos += hash[haystack.charCodeAt(pos + needle.length - 1)]          }      }        return -1  };

結果：

  • 74/74 cases passed (68 ms)
  • Your runtime beats 79.76 % of javascript submissions
  • Your memory usage beats 16.14 % of javascript submissions (35.4 MB)
  • 時間複雜度 O(n)

Ⅶ.Sunday 演算法

演算法說明：

它的思想跟 BM 演算法 相似，但是它是從前往後匹配，匹配失敗時關注主串內參與匹配的後一位字元。如果該字元不存在匹配字元中，則多偏移一位；如果存在，則偏移匹配串長度減該字元最右出現的位置。

程式碼：

結果：

  • 74/74 cases passed (56 ms)
  • Your runtime beats 98.3 % of javascript submissions
  • Your memory usage beats 74.1 % of javascript submissions (33.6 MB)
  • 時間複雜度 O(n)

思考總結

就理解的難易度來講，我建議先看 Sunday 演算法 和 Horspool 演算法，不過 RMP 演算法 的匹配思路打開了眼界，利用後綴前綴來處理問題。這裡把常見的字元串演算法都做了一次嘗試，整體下來收穫頗豐。

（完）

本文為原創文章，可能會更新知識點及修正錯誤，因此轉載請保留原出處，方便溯源，避免陳舊錯誤知識的誤導，同時有更好的閱讀體驗
如果能給您帶去些許幫助，歡迎 ⭐️star 或 ✏️ fork
(轉載請註明出處：https://chenjiahao.xyz)

VirMach 便宜 VPS

QNews

QNews