本文為Python算法題集之一的代碼示例

題22：單詞搜索

1. 示例說明

• 給定一個 m x n 二維字符網格 board 和一個字符串單詞 word 。如果 word 存在于網格中，返回 true ；否則，返回 false 。

  單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重復使用。

  示例 1：

  

  輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
  輸出：true
  

  示例 2：

  

  輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
  輸出：true
  

  示例 3：

  

  輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
  輸出：false
  

  提示：

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 僅由大小寫英文字母組成

  **進階：**你可以使用搜索剪枝的技術來優化解決方案，使其在 board 更大的情況下可以更快解決問題？

---

2. 題目解析

- 題意分解

1. 本題是在矩陣內檢查是否有相鄰元素組成對應單詞
2. 矩陣內每一個元素最多有4個方向，考慮到搜索進入方向，從第二個字母開始，最多有3個方向，可以用回溯法解題
3. 回溯法（探索與回溯法）是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇并不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法。

- 優化思路

1. 通常優化：減少循環層次

2. 通常優化：增加分支，減少計算集

3. 通常優化：采用內置算法來提升計算速度

4. 分析題目特點，分析最優解

   1. 可以使用字典進行字符檢測，只有存在檢測單詞所有字符的矩陣才展開搜索

   2. 可以使用原始矩陣保存檢測狀態，也可以另外使用矩陣保存檢測狀態

---

- 測量工具

• 本地化測試說明：LeetCode網站測試運行時數據波動很大【可把頁面視為功能測試】，因此需要本地化測試解決數據波動問題
• CheckFuncPerf（本地化函數用時和內存占用測試模塊）已上傳到CSDN，地址：Python算法題集_檢測函數用時和內存占用的模塊
• 本題本地化超時測試用例自己生成，詳見章節【最優算法】，代碼文件包含在【相關資源】中

---

3. 代碼展開

1) 標準求解【原始矩陣狀態+回溯】

使用原始矩陣保存檢測狀態【當前已檢測路徑值設置為’'】，實現回溯

頁面功能測試，馬馬虎虎，超過76%

import CheckFuncPerf as cfpclass Solution:def exist_base(self, board, word):def dfs_backtrack(irow, icol, icheckpos):if not 0 <= irow < len(board) or not 0 <= icol < len(board[0]) or \board[irow][icol] != word[icheckpos]:return Falseif icheckpos == len(word) - 1:return Trueboard[irow][icol] = ''result = dfs_backtrack(irow + 1, icol, icheckpos + 1) or \dfs_backtrack(irow - 1, icol, icheckpos + 1) or \dfs_backtrack(irow, icol + 1, icheckpos + 1) or \dfs_backtrack(irow, icol - 1, icheckpos + 1)board[irow][icol] = word[icheckpos]return resultfor irow in range(len(board)):for icol in range(len(board[0])):if board[irow][icol] == word[0] and dfs_backtrack(irow, icol, 0):return Truereturn FalseaSolution = Solution()
checkmapmatrix = copy.deepcopy(mapmatrix)
result = cfp.getTimeMemoryStr(aSolution.exist_base, checkmapmatrix, checkword)
print(result['msg'], '執行結果 = {}'.format(result['result']))# 運行結果
函數 exist_base 的運行時間為 24.00 ms；內存使用量為 684.00 KB 執行結果 = True

2) 改進版一【字典檢測+原始矩陣狀態+回溯】

使用字典進行字符集檢測，符合要求的才開始回溯；回溯中使用原始矩陣保存檢測狀態

頁面功能測試，性能卓越，超越95%

import CheckFuncPerf as cfpclass Solution:def exist_ext1(self, board, word):def preCheck():preDict = {}for chr in word:if chr in preDict:preDict[chr] += 1else:preDict[chr] = 1for arow in board:for achr in arow:if achr in preDict and preDict[achr] > 0:preDict[achr] -= 1for aval in preDict.values():if aval > 0:return Falsereturn Truedef dfs_backtrack(irow, icol, icheckpos):if icheckpos == imaxlen:return Trueif 0 <= irow < imaxrow and 0 <= icol < imaxcol and board[irow][icol] == word[icheckpos]:board[irow][icol] = ''for inextrow, inextcol in (irow, icol + 1), (irow, icol - 1), \(irow + 1, icol), (irow - 1, icol):if dfs_backtrack(inextrow, inextcol, icheckpos + 1):return Trueboard[irow][icol] = word[icheckpos]return Falseif preCheck() == False:return Falseimaxrow, imaxcol, imaxlen = len(board), len(board[0]), len(word)for irow in range(imaxrow):for icol in range(imaxcol):if board[irow][icol] == word[0] and dfs_backtrack(irow, icol, 0):return Truereturn FalseaSolution = Solution()
checkmapmatrix = copy.deepcopy(mapmatrix)
result = cfp.getTimeMemoryStr(aSolution.exist_ext1, checkmapmatrix, checkword)
print(result['msg'], '執行結果 = {}'.format(result['result']))# 運行結果
函數 exist_ext1 的運行時間為 25.01 ms；內存使用量為 644.00 KB 執行結果 = True

3) 改進版二【矩陣狀態+回溯】

使用多維列表結構保存檢測路徑狀態，實現回溯

頁面功能測試，性能良好，超過88%

import CheckFuncPerf as cfpclass Solution:def exist_ext2(self, board, word):imaxrow, imaxcol, imaxlen = len(board), len(board[0]), len(word)path = [''] * imaxlenmap_check = [[False] * imaxcol for x in range(imaxrow)]def dfs_backtrack(icheckpos, irow, icol, imaxrow, imaxcol, board, word, checkmatrix):if irow < 0 or irow >= imaxrow or icol < 0 or icol >= imaxcol:return Falseif checkmatrix[irow][icol]:return Falseif board[irow][icol] != word[icheckpos]:return Falseif icheckpos == imaxlen - 1:return Truepath[icheckpos] = word[icheckpos]checkmatrix[irow][icol] = Trueif dfs_backtrack(icheckpos + 1, irow - 1, icol, imaxrow, imaxcol, board, word, checkmatrix) or \dfs_backtrack(icheckpos + 1, irow + 1, icol, imaxrow, imaxcol, board, word, checkmatrix) or \dfs_backtrack(icheckpos + 1, irow, icol - 1, imaxrow, imaxcol, board, word, checkmatrix) or \dfs_backtrack(icheckpos + 1, irow, icol + 1, imaxrow, imaxcol, board, word, checkmatrix):return Truecheckmatrix[irow][icol] = Falsepath[icheckpos] = ''return Falsefor irow in range(imaxrow):for icol in range(imaxcol):if dfs_backtrack(0, irow, icol, imaxrow, imaxcol, board, word, map_check):return Truereturn FalseaSolution = Solution()
checkmapmatrix = copy.deepcopy(mapmatrix)
result = cfp.getTimeMemoryStr(aSolution.exist_ext2, checkmapmatrix, checkword)
print(result['msg'], '執行結果 = {}'.format(result['result']))# 運行結果
函數 exist_ext2 的運行時間為 43.01 ms；內存使用量為 384.00 KB 執行結果 = True

---

4. 最優算法

根據本地日志分析，最優算法為第1種方式【原始矩陣狀態+回溯】exist_base

本題測試數據，似乎能推出以下結論：

1. 字典過濾檢測性能消耗極小
2. 額外的數據存儲，帶來額外的性能消耗
3. 在檢測集合和字符串多樣化的情況下，第二種算法其實是會表現更好

import random, copy
imaxrow, imaxcol, checkword = 500, 300, ''
mapmatrix=[['' for x in range(imaxcol)] for y in range(imaxrow)]
words = list('abcdefghijklmnopqrstuvwxyz')
for irow in range(imaxrow):for icol in range(imaxcol):mapmatrix[irow][icol] = random.choice(words)
for iIdx in range(1, min(imaxrow, imaxcol)):checkword += mapmatrix[imaxrow-iIdx][imaxcol-iIdx] + mapmatrix[imaxrow-iIdx][imaxcol-iIdx-1]
aSolution = Solution()
checkmapmatrix = copy.deepcopy(mapmatrix)
result = cfp.getTimeMemoryStr(aSolution.exist_base, checkmapmatrix, checkword)
print(result['msg'], '執行結果 = {}'.format(result['result']))
checkmapmatrix = copy.deepcopy(mapmatrix)
result = cfp.getTimeMemoryStr(aSolution.exist_ext1, checkmapmatrix, checkword)
print(result['msg'], '執行結果 = {}'.format(result['result']))
checkmapmatrix = copy.deepcopy(mapmatrix)
result = cfp.getTimeMemoryStr(aSolution.exist_ext2, checkmapmatrix, checkword)
print(result['msg'], '執行結果 = {}'.format(result['result']))# 算法本地速度實測比較
函數 exist_base 的運行時間為 24.00 ms；內存使用量為 684.00 KB 執行結果 = True
函數 exist_ext1 的運行時間為 25.01 ms；內存使用量為 644.00 KB 執行結果 = True
函數 exist_ext2 的運行時間為 43.01 ms；內存使用量為 384.00 KB 執行結果 = True

---

5. 相關資源

本文代碼已上傳到CSDN，地址：Python算法題源代碼_LeetCode(力扣)_單詞搜索

一日練，一日功，一日不練十日空

may the odds be ever in your favor ~