專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

以前我面試的時候無論結果如何都不會自動和hr聯系，因為我覺得如果過了hr肯定會聯系我，如果沒過，就算我主動聯系也沒用。今天看到一個00后的學生和hr的對話讓我感覺到啥叫高情商，看似啥都沒問，實則啥都問了。

在網上也經常看到不少面試后主動聯系HR而爭取到offer的，這種情況下一般是候選人都比較優秀，hr還在猶豫該選誰，這個時候主動問候還是有機會的。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第79題：單詞搜索。

問題描述

來源：LeetCode第79題

難度：中等

給定一個 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 = "ABCB" 輸出：false

• m == board.length

• n = board[i].length

• 1 <= m, n <= 6

• 1 <= word.length <= 15

• board 和 word 僅由大小寫英文字母組成

問題分析

這題是讓判斷給定的單詞是否在二維網格中，這是一道搜索問題，前面我們也講過各種搜索算法：

(BFS)

這題我們可以使用回溯算法，對于當前點沿著他的上下左右 4 個方向查找，如果最后能找到給定的單詞就返回true，否則就返回false，如下圖所示。

這里要注意同一單元格類的字母不能被重復使用，所以我們查找之后還需要標記一下。由于單詞的起始字母在網格中的哪個位置我們并不知道，所以需要以網格中的每一個位置為起始點進行查找。

JAVA：

public boolean exist(char[][] board, String word) {     char[] words = word.toCharArray();     // 遍歷網格的所有位置，以每一個位置為起始點進行查找。     for (int i = 0; i < board.length; i++) {         for (int j = 0; j < board[0].length; j++) {             // 從(i,j)這個坐標開始查找，如果找到直接返回true。             if (dfs(board, words, i, j, 0))                 return true;         }     }     return false; } // (i,j)表示當前查找的坐標，index表示查找單詞的第幾個字母。 boolean dfs(char[][] board, char[] words, int i, int j, int index) {     // 邊界的判斷，如果越界直接返回false。index表示的是查找到字符串words的第幾個字符，     // 如果這個字符不等于board[i][j]，說明驗證這個坐標路徑是走不通的，直接返回false。     if (i >= board.length || i < 0 || j >= board[0].length             || j < 0 || board[i][j] != words[index])         return false;     // 如果words的每個字符都查找完了，直接返回true     if (index == words.length - 1)         return true;     // 把當前坐標的值保存下來，為了在最后復原。     char tmp = board[i][j];     // 修改當前坐標的值，主要為了防止當前網格被重復查找。     board[i][j] = '.';     // 走遞歸，沿著當前坐標的上下左右4個方向查找     boolean res = dfs(board, words, i - 1, j, index + 1)// 上             || dfs(board, words, i + 1, j, index + 1)// 下             || dfs(board, words, i, j - 1, index + 1)// 左             || dfs(board, words, i, j + 1, index + 1);// 右     // 遞歸之后再把當前的坐標復原。     board[i][j] = tmp;     return res;// 返回查找的結果。 }

C++：

public:     bool exist(vector char >>& board, string word) {         // 遍歷網格的所有位置，以每一個位置為起始點進行查找。         for (int i = 0; i < board.size(); i++) {             for (int j = 0; j < board[0].size(); j++) {                 // 從(i,j)這個坐標開始查找，如果找到直接返回true。                 if (dfs(board, word, i, j, 0))                     return true;             }         }         return false;     }     // (i,j)表示當前查找的坐標，index表示查找單詞的第幾個字母。     bool dfs(vector char >>& board, string word, int i, int j, int index) {         // 邊界的判斷，如果越界直接返回false。index表示的是查找到字符串word的第幾個字符，         // 如果這個字符不等于board[i][j]，說明驗證這個坐標路徑是走不通的，直接返回false。         if (i >= board.size() || i < 0 || j >= board[0].size()                 || j < 0 || board[i][j] != word[index])             return false;         // 如果words的每個字符都查找完了，直接返回true         if (index == word.size() - 1)             return true;         // 把當前坐標的值保存下來，為了在最后復原。         char tmp = board[i][j];         // 修改當前坐標的值，主要為了防止當前網格被重復查找。         board[i][j] = '.';         // 走遞歸，沿著當前坐標的上下左右4個方向查找         bool res = dfs(board, word, i - 1, j, index + 1)// 上                 || dfs(board, word, i + 1, j, index + 1)// 下                 || dfs(board, word, i, j - 1, index + 1)// 左                 || dfs(board, word, i, j + 1, index + 1);// 右         // 遞歸之后再把當前的坐標復原。         board[i][j] = tmp;         return res;// 返回查找的結果。     }

Python：

# 79. 單詞搜索 def exist(self, board: List[List[str]], word: str) -> bool:     def dfs(i: int, j: int, index: int):         if index == len(word):             return True  # 單詞的所有字符全部查找完了。         # 不能越界，不能訪問到矩陣的外面         if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):             return False         # 如果查找字符不一樣，返回false。         if board[i][j] != word[index]:             return False         tmp = board[i][j]  # 把原來字符記錄下來         board[i][j] = '#'  # 表示已經被訪問過了，防止重復訪問。         exist = (dfs(i - 1, j, index + 1)  # 上                  or dfs(i + 1, j, index + 1)  # 下                  or dfs(i, j - 1, index + 1)  # 左                  or dfs(i, j + 1, index + 1))  # 右         board[i][j] = tmp  # 回溯算法，還原，撤銷選擇         return exist     # 以網格的任何一個位置為起始點進行查找。     for i in range(0, len(board)):         for j in range(0, len(board[i])):             if dfs(i, j, 0):                 return True     return False  # 如果都查找不到，返回false。

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。