首页 > 代码库 > Leetcode: Word Search

Leetcode: Word Search

2024-07-05 17:35:09   226人阅读

DFS算法，非常容易TLE，需要一个boolean矩阵来记录是否访问过某个节点。

写DFS主要就是两个方法：用recursion或者Stack, 用recursion会带来time和memory的cost增加，而且因为要用矩阵做argument, 所以非常担心TLE或者MLE的问题。但是用recursion就比较容易使用boolean矩阵，可以比较容易地对某个节点设置visited或者unvisited。而用stack来写呢，cost会小，但是很难用boolean矩阵来设置之前访问过的某个节点为unvisited。所以思来想去，还是用recursion来写。

 1 public class Solution {
 2     private int m;
 3     private int n;
 4     public boolean exist(char[][] board, String word) {
 5         m = board.length;
 6         n = board[0].length;
 7         boolean[][] visited = new boolean[m][n];
 8         for (int i = 0; i < m; i++) {
 9             for (int j = 0; j < n; j++) {
10                 if (board[i][j] == word.charAt(0)) {
11                     if (dfs(board, i, j, visited, word, 0)) return true;
12                 } 
13             }
14         }
15         return false;
16     }
17     
18     public boolean dfs(char[][] board, int x, int y, boolean[][] visited, String word, int k) {
19         if (k == word.length()) return true;
20         if (x < 0 || y < 0 || x >= m || y >= n) return false;
21         if (visited[x][y] == true) return false;
22         if (board[x][y] != word.charAt(k)) return false;
23         visited[x][y] = true;
24         boolean res = dfs(board, x, y-1, visited, word, k+1)
25                     || dfs(board, x, y+1, visited, word, k+1)
26                     || dfs(board, x-1, y, visited, word, k+1)
27                     || dfs(board, x+1, y, visited, word, k+1); 
28         visited[x][y] = false;
29         return res;
30     }
31 }

下面这个code TLE了，但是跟上面那个都没什么区别，不知道为什么

public class Solution {
    private int m;
    private int n;
    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (dfs(board, i, j, visited, word, 0)) return true;
                } 
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] board, int x, int y, boolean[][] visited, String word, int k) {
        boolean bool1 = false, bool2 = false, bool3 = false, bool4 = false;
        if (k == word.length()) return true;
        if (x < 0 || y < 0 || x >= m || y >= n) return false;
        if (visited[x][y] == true) return false;
        if (board[x][y] != word.charAt(k)) return false;
        visited[x][y] = true;
        bool1 = dfs(board, x, y-1, visited, word, k+1); //left
        bool2 = dfs(board, x, y+1, visited, word, k+1); //right
        bool3 = dfs(board, x-1, y, visited, word, k+1); //up
        bool4 = dfs(board, x+1, y, visited, word, k+1); //down
        visited[x][y] = false;
        return bool1 || bool2 || bool3 || bool4;
    }
}

再贴一个用stack写的DFS，但是想不出来怎么设置之前访问过的一个节点为unvisited

 1 public class Solution {
 2     public boolean exist(char[][] board, String word) {
 3         int m = board.length;
 4         int n = board[0].length;
 5         Stack<Integer> toVisit = new Stack<Integer>();
 6         boolean[][] visited = new boolean[m][n];
 7         if (word == "") return true;
 8         if (m == 0 && n == 0 && word != "") return false;
 9         for (int i = 0; i < m; i++) {
10             for (int j = 0; j < n; j++) {
11                 if (board[i][j] == word.charAt(0)) {
12                     toVisit.push(i * n + j);
13                 } 
14             }
15         }
16         
17         int k = 0;
18         while (!toVisit.empty()) {
19             int root = toVisit.pop();
20             int x = root / n;
21             int y = root % n;
22             visited[x][y] = true;
23             if (k == word.length() - 1) return true;
24             if (y > 0 && visited[x][y-1] == false && board[x][y-1] == word.charAt(k+1)) { //left
25                 toVisit.push(x * n + y - 1);
26                 k++;
27             }
28             if (y < n && visited[x][y+1] == false && board[x][y+1] == word.charAt(k+1)) { //right
29                 toVisit.push(x * n + y + 1);
30                 k++;
31             }
32             if (x > 0 && visited[x-1][y] == false && board[x-1][y] == word.charAt(k+1)) { //up
33                 toVisit.push((x - 1) * n + y);
34                 k++;
35             }
36             if (x < m && visited[x+1][y] == false && board[x+1][y] == word.charAt(k+1)) { //down
37                 toVisit.push((x + 1) * n + y);
38                 k++;
39             }
40         }
41         return false;
42     }
43 }

 


联系
我们