LeetCode 79. 單詞搜索【c++/java詳細題解】

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 僅由大小寫英文字母組成

2、思路

(回溯) O ( n 2 3 k ) O(n^2 3^k) O(n23k)

深度優先搜索，我們定義這樣一種搜索順序，即先列舉單詞的起點，然后依次列舉單詞的每個字母，在這個程序中需要將已經使用過的字母改成一個特殊字母，以避免重復使用字符，

遞回函式設計：

bool dfs(vector<vector<char>>& board, string& word,int u,int x,int y)

u代表當前列舉到了目標單詞word第u個位置，

x，y是當前搜索到的二維字符網格的橫縱坐標，

搜索程序如下：

• 1、在二維字符網格中列舉每個單詞的起點，
• 2、從該起點出發向四周搜索單詞word，并記錄此時列舉到單詞word的第u個位置 ( u從0開始)，
• 3、如果當前搜索的位置(x,y)的元素board[x][y] == word[u],則繼續向四周搜索，
• 4、直到列舉到單詞word的最后一個字母回傳ture，否則回傳false，

遞回邊界：

• 1、當搜索程序出現當前位置board[x][y] != word[u] ，說明當前路徑不合法，回傳false，
• 2、u == word.size() - 1,成功搜索到單詞末尾，回傳true，

實作細節：

• 1、搜索過的位置繼續搜索下一層時，需要對當前位置進行標識，表示已經搜索

• 2、可以使用偏移陣列來簡化代碼，

時間復雜度分析： 單詞起點一共有 n 2 n^2 n2 個，單詞的每個字母一共有上下左右四個方向可以選擇，但由于不能走回頭路，所以除了單詞首字母外，僅有三種選擇，所以總時間復雜度是 O ( n 2 3 k ) O(n^2 3^k) O(n23k) ，

3、c++代碼

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j < board[i].size(); j++)
                if(dfs(board,word,0,i,j)) return true;
        return false;        
    }
    int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1}; //方向陣列
    bool dfs(vector<vector<char>>& board, string& word,int u,int x,int y)
    {
        if(board[x][y] != word[u]) return false;
        if(u == word.size() - 1)   return true;
        char t = board[x][y];
        board[x][y] = '.';
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            //出界或者走到已經搜索過的位置
            if(a < 0 || a >= board.size() || b < 0 || b >= board[0].size() || board[a][b] == '.')  continue;
            if(dfs(board,word,u+1,a,b)) return true;
        }
        board[x][y] = t;
        return false;
    }
};

4、java代碼

class Solution {
    public boolean exist(char[][] board, String word) {
        for(int i = 0; i < board.length; i++)
            for(int j = 0; j < board[i].length; j++)
                if(dfs(board,word,0,i,j)) return true;
        return false;   
    }
    int[] dx = new int[]{-1,0,1,0}, dy = new int[]{0,1,0,-1};
    boolean dfs(char[][] board, String word,int u,int x,int y)
    {
        if(board[x][y] != word.charAt(u)) return false;
        if(u == word.length() - 1)   return true;
        char t = board[x][y];
        board[x][y] = '.';
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || a >= board.length|| b < 0 || b >= board[0].length || board[a][b] == '.')  continue;
            if(dfs(board,word,u+1,a,b)) return true;
        }
        board[x][y] = t;
        return false;
    }
}

原題鏈接：79. 單詞搜索