leetcode 79. Word Search | 79. 单词搜索（回溯+DFS）

亦凉 2022-08-28 09:58 186阅读 0赞

## 题目 ##

[https://leetcode.com/problems/word-search/][https_leetcode.com_problems_word-search]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

回溯 + DFS，回溯是有后效性的，所以不能转化为 DP

class Solution { 
        int M;
        int N;
    
        public boolean exist(char[][] board, String word) { 
            M = board.length;
            N = board[0].length;
            for (int i = 0; i < M; i++) { 
                for (int j = 0; j < N; j++) { 
                    if (dfs(word, 0, i, j, board, new boolean[M][N])) return true;
                }
            }
            return false;
        }
    
        public boolean dfs(String word, int index, int i, int j, char[][] board, boolean[][] visited) { 
            if (index == word.length()) return true;
            if (i < 0 || i == M || j < 0 || j == N || visited[i][j] || board[i][j] != word.charAt(index)) return false;
    
            visited[i][j] = true;
            boolean result = dfs(word, index + 1, i + 1, j, board, visited) ||
                    dfs(word, index + 1, i - 1, j, board, visited) ||
                    dfs(word, index + 1, i, j + 1, board, visited) ||
                    dfs(word, index + 1, i, j - 1, board, visited);
            visited[i][j] = false;
    
            return result;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode.com_problems_word-search]: https://leetcode.com/problems/word-search/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/0cec1dd79d1a4b29be3b690f510c3620.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/3ff97648f2c247c4ba2c74faf17b8f93.png