79-单词搜索

LeetCode 79. Word Search

LeetCode-79

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

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

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

method

深度优先搜索+回溯

直接修改元素，回溯再复原，先递归再判断

bool dfs(vector<vector<char>>& board, string word, int i, int j, int index) {
    if (index == word.size()) return true;  // 这两个if不能调换，因为index会越界
    // 不能写成index==word.size()-1就返回，因为最后一个元素还没判断
    if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[index])
        return false;
    char tmp = board[i][j];
    board[i][j] = '0';  // 表示这个元素被用了
    bool res = dfs(board, word, i - 1, j, index + 1) || 
            dfs(board, word, i + 1, j, index + 1) || 
            dfs(board, word, i, j - 1, index + 1) || 
            dfs(board, word, i, j + 1, index + 1);
    board[i][j] = tmp;  // 回溯复原
    return res;
}
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 (dfs(board, word, i, j, 0))
                return true;
        }
    }
    return false;
}

也可以先判断，再递归

int next[4][2] = {{-1,0}, {1, 0}, {0, -1}, {0, 1}};
bool dfs(vector<vector<char>>& board, string word, int i, int j, int index) {
    if (board[i][j] != word[index]) return false;
    if (index == word.size() - 1) return true;  // 先判断再走，就只会走到最后一个字符
    char tmp = board[i][j];
    board[i][j] = '0';
    for (int k = 0; k < 4; k++) {
        int nx = i + next[k][0];
        int ny = j + next[k][1];
        if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size() && board[nx][ny] != '.') {  // 这里不判断是否已走过也行
            if (dfs(board, word, nx, ny, index + 1)) return true;
        }      
    }
    board[i][j] = tmp;
    return false;
}
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 (dfs(board, word, i, j, 0))
                return true;
        }
    }
    return false;
}