leetcode算法练习【79】单词搜索

朴灿烈づ我的快乐病毒、 2023-02-11 13:26 15阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：回溯法
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
    
    单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
    
     
    
    示例:
    
    board =
    [
      ['A','B','C','E'],
      ['S','F','C','S'],
      ['A','D','E','E']
    ]
    
    给定 word = "ABCCED", 返回 true
    给定 word = "SEE", 返回 true
    给定 word = "ABCB", 返回 false
     
    
    提示：
    
    board 和 word 中只包含大写和小写英文字母。
    1 <= board.length <= 200
    1 <= board[i].length <= 200
    1 <= word.length <= 10^3

#### 方案：回溯法 ####

class Solution { 
            private int[][] tmp;
            private char[][] board;
            private String word;
            private int row;
            private int col;
    
            public boolean exist(char[][] board, String word) { 
                // 回朔法，像走迷宫
    
                this.row = board.length;
                if (this.row < 1)
                    return false;
                this.col = board[0].length;
    
                this.word = word;
                this.board = board;
                this.tmp = new int[row][col];
                // 从每格开始当头匹配
                for (int i = 0; i < row; i++) { 
                    for (int j = 0; j < col; j++) { 
    
                        if (backtrack(i, j, 0))
                            return true;
    
                    }
                }
    
                return false;
    
            }
    
            public boolean backtrack(int i, int j, int k) { 
    
                if (board[i][j] == word.charAt(k)) { 
                    if(k == word.length()-1) return true;
                    // next turn 上下左右寻找
                    tmp[i][j] = 1;
                    if (i > 0 && tmp[i - 1][j] == 0 && backtrack(i - 1, j, k + 1)) { 
                        return true;
                    } else if (i < row - 1 && tmp[i + 1][j] == 0 && backtrack(i + 1, j, k + 1)) { 
                        return true;
                    } else if (j > 0 && tmp[i][j - 1] == 0 && backtrack(i, j - 1, k + 1)) { 
                        return true;
                    } else if (j < col - 1 && tmp[i][j + 1] == 0 && backtrack(i, j + 1, k + 1)) { 
                        return true;
                    }
                    tmp[i][j] = 0;
                }
                return false;
            }
    
        }

##### 复杂度计算 #####

*  时间复杂度：O(mns),mn为数组长宽，s为字符串长
 *  空间复杂度：O(mn)

[Git]: https://github.com/ch98road/leetcode