Leetcode 79 单词搜索

1. 题目

79. 单词搜索 (opens new window)

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

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

2. 代码

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size();
        int m = board[0].size();
        for(int i = 0; i<n; ++i){
            for(int j = 0; j<m; ++j){
                if(board[i][j] == word[0] && dfs(i, j, board, word, 0)){
                    return true;
                }
            }
        }
        return false;
    }
private:
    bool dfs(int x, int y, vector<vector<char>>& board, string& word, int index){
        int n = board.size();
        int m = board[0].size();

        if(x<0 || x>=n || y<0 || y>=m || board[x][y] != word[index]){
            return false;
        }
        if(index == word.size() - 1){
            return true;
        }
        char c = board[x][y];
        board[x][y] = '\0';
        if(dfs(x + 1, y, board, word, index + 1)
                || dfs(x - 1, y, board, word, index + 1)
                || dfs(x, y + 1, board, word, index + 1)
                || dfs(x, y - 1, board, word, index + 1)){
            return true;
        }
        board[x][y] = c;
        return false;
    }
};

3. 思路

感觉思路很简单，这里贴一下修改过程。本来交上是60ms 很慢，后面改成了24ms。

60ms优化到24ms的心得：

1. 去掉循环，直接四个方向用||连接判断
2. 不用used，在原board上修改（当然这样不一定规范
3. 结束条件放到检查边界后面，因为结束条件true的次数很少，放前面开销大
4. 使用if(dfs()) return true;这种模式，可以节约flag变量