79. Word Search (Medium)

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,

Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Solution: DFS (Backtracking)

76ms $$O(n^2)$$

这道题是典型的深度优先遍历DFS的应用，原二维数组就像是一个迷宫，可以上下左右四个方向行走，我们以二维数组中每一个数都作为起点和给定字符串做匹配，我们还需要一个和原数组等大小的visited数组，是bool型的，用来记录当前位置是否已经被访问过，因为题目要求一个cell只能被访问一次。如果二维数组board的当前字符和目标字符串word对应的字符相等，则对其上下左右四个邻字符分别调用DFS的递归函数，只要有一个返回true，那么就表示可以找到对应的字符串，否则就不能找到，具体看代码实现如下：

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (word.empty()) return true;
        if (board.empty() || board[0].empty()) return false;
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dfs(board, word, 0, i, j, visited)) return true;
            }
        }
        return false;
    }
private:
    bool dfs(vector<vector<char>>& board, string& word, int idx, int i, int j, vector<vector<bool>>& visited) {
        if (idx == word.size()) return true;
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || visited[i][j] || board[i][j] != word[idx]) return false;
        visited[i][j] = true;
        bool res = dfs(board, word, idx+1, i-1, j, visited) || 
            dfs(board, word, idx+1, i+1, j, visited) || 
            dfs(board, word, idx+1, i, j-1, visited) || 
            dfs(board, word, idx+1, i, j+1, visited);
        visited[i][j] = false;
        return res;
    }
};

version 2: 13 ms 在原来的board上改

class Solution {
    vector<int> dirs = {0,-1,0,1,0};
    bool dfs(vector<vector<char>>& board, string& word, int pos, int row, int col) {
        if (pos == word.size()) return true;
        for (int i = 0; i < 4; ++i) {
            int x = row+dirs[i], y = col+dirs[i+1];
            if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] == word[pos]) {
                board[x][y] = '\0';
                if (dfs(board, word, pos+1, x, y)) return true;
                board[x][y] = word[pos];
            }
        }
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                if (board[i][j] == word[0]) {
                    board[i][j] = '\0';
                    if (dfs(board, word, 1, i, j)) return true;
                    board[i][j] = word[0];
                }
            }
        }
        return false;
    }
};

16ms no need to store extra visited board

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (word.empty()) return true;
        if (board.empty() || board[0].empty()) return false;
        m = board.size(); n = board[0].size();

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dfs(board, word.c_str(), i, j)) return true;
            }
        }
        return false;
    }
private:
    int m, n;
    bool dfs(vector<vector<char>>& board, const char* word, int i, int j) {
        if(*word == '\0') return true;
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == '\0' || board[i][j] != *word) return false;
        char c = board[i][j];
        board[i][j] = '\0';
        bool res = dfs(board, word+1, i-1, j) || 
            dfs(board, word+1, i+1, j) || 
            dfs(board, word+1, i, j-1) || 
            dfs(board, word+1, i, j+1);
        board[i][j] = c;
        return res;
    }
};