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

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

最近關于大疆不強制 9 點上班，強制 9 點下班的消息沖上熱搜，一到晚上9點，大疆的主管和HR分三輪趕人下班，禁止員工加班，9點以后，HRBP開始掃雷式趕人，他們背著“必須清場”的KPI。深圳總部實行趕人策略，上海區域更直截了當，辦公樓到晚上9點準時關燈。

而美的從上周起就開始提倡各部門領導嚴謹控制加班，規定18:20不允許有人還在公司加班，同時也禁止了員工就餐后再返回工位繼續加班的現象。一到下班時間，HR就會挨著部門催促員工抓緊時間下班。

這么好的事早幾年就應該執行，本來三個人的活硬是讓兩個人加班干出來，回歸到8小時工作制就會多出很多崗位，現在每年有一千多萬畢業大學生，實行8小時工作制也可以促進大學生就業率。

有的人可能會擔心，制造行業員工的收入主要靠加班，如果沒有加班，只拿基本工資，估計難以生存，我覺得吧這個事有利有弊，但我還是支持8小時工作制。

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

來看下今天的算法題，這題是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 僅由大小寫英文字母組成

問題分析

這題讓判斷網格中是否存在要查找的單詞，也沒有告訴單詞的起始位置在網格中的什么地方，我們以網格中的每一個位置當做起始位置來進行搜索。題中說的相鄰是指水平和垂直方向，也就是從每個位置的上下左右四個方向進行搜索。

這是一道回溯算法題，如果從某個位置開始搜索，要注意一個位置不能重復搜索，所以搜索過之后要把它標記一下，題中說了字符串僅由大小寫英文字母組成，標記的字符只要不是大小寫英文字母就可以。沿著某條路徑搜索完之后如果沒有找到，需要撤銷標記。

JAVA：

public boolean exist(char[][] board, String word) {     char[] chars = 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, i, j, chars, 0))                 returntrue;         }     returnfalse; } // 方向數組 int[][] dirs = newint[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; private boolean dfs(char[][] board, int i, int j, char[] word, int index) {     if (index == word.length) // 要查找字符串中的所有字符都查找完了。         returntrue;     // 不能越界     if (i < 0 || j < 0 || i >= board.length || j >= board[0].length)         returnfalse;     if (board[i][j] != word[index])         returnfalse;     char tmp = board[i][j];// 先把當前位置的字符保存下來     board[i][j] = '#';// 修改當前位置的字符，只要不是大小寫字符都可以     for (int[] dir : dirs) {// 沿著當前位置的上下左右四個方向查找。         int x = i + dir[0];         int y = j + dir[1];         // 如果有一個方向能查找成功，直接返回true         if (dfs(board, x, y, word, index + 1))             returntrue;     }     board[i][j] = tmp;// 還原。     returnfalse; }

C++：

public:     bool exist(vector

 > &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, i, j, word, 0))                     returntrue;             }         }         returnfalse;     }     constint dirs[4][2] = {{0,  1},                             {0,  -1},                             {1,  0},                             {-1, 0}}; private:     bool dfs(vector

 > &board, int i, int j, string &word, int index) {         if (index == word.size()) // 要查找字符串中的所有字符都查找完了。             returntrue;         // 不能越界         if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size())             returnfalse;         if (board[i][j] != word[index])             returnfalse;         char tmp = board[i][j];// 先把當前位置的字符保存下來         board[i][j] = '#';  // 修改當前位置的字符，只要不是大小寫字符都可以         for (constauto &dir: dirs) {// 沿著當前位置的上下左右四個方向查找。             int x = i + dir[0];             int y = j + dir[1];             // 如果有一個方向能查找成功，直接返回true             if (dfs(board, x, y, word, index + 1))                 returntrue;         }         board[i][j] = tmp;  // 恢復原字符         returnfalse;     }

筆者簡介

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