079.WordSearch.md

tags: Array, Backtracking, DFS

#LeetCode 79 Word Search

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']
]

word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false.

Difficulty
Medium

Similar Problems
[LeetCode 212] Word Search II

Analysis

This is a basic classic backtracking and DFS problem.

Idea

We do a DFS search for each point to see if it can produce a matching word, the trick is how we optimize the search and avoid the unnecessary calculation (e.g. once we have found the target word we should stop searching immediately). We need to mark the visited number to avoid re-walking it, we use XOR operation to temparily change the visited number to another number and use XOR to get it back after we done a dfs.

Key pointes:

• backtracking/DFS algorithm, need to search four directions
• use a temp variable to store how many characters have been visited
• use XOR operation with 255 to flag the restore the visited element
• stop condition: word length, board boundary

The termination condition:

• If board[i][j] != word[index], return false
• If the len of path we have walked is overpass the boundary of the board, this means we still haven't found the target word, return false
• If the len of path we have walked is larger than the length of the target word, this means we have already found the target word, return true.

Solutions

1. Cpp

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.size() == 0) return false;
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                bool isExisted = search(board, i, j, word, 0);  // i, j is the start point of the search
                if(isExisted) return true;                      // return true as soon as we find an existance
            }
        }
        return false;
    }
    
private:
    bool search(vector<vector<char>>& board, int i, int j, string word, int idx){
        if(idx >= word.length()) return true;
        if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word.at(idx)) return false;
        board[i][j] ^= 255; // use xor to flag the visited number
        bool res = search(board, i-1, j, word, idx+1) || search(board, i+1, j, word, idx+1) || search(board, i, j-1, word, idx+1) || search(board, i, j+1, word, idx+1);
        board[i][j] ^= 255; // xor again to get it back
        return res;
    }
};

2. Go solution

func exist(board [][]byte, word string) bool {
    if len(board) == 0 {
        return false
    }

    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            if isExist := search_word(board, i, j, word, 0); isExist {
                return true
            }
        }
    }

    return false
}

func search_word(board [][]byte, i, j int, word string, idx int) bool {
    if idx >= len(word) {
        return true
    }
    if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || board[i][j] != word[idx] {
        return false
    }

    board[i][j] ^= 255
    res := search_word(board, i-1, j, word, idx+1) || search_word(board, i+1, j, word, idx+1) || search_word(board, i, j-1, word, idx+1) || search_word(board, i, j+1, word, idx+1)
    board[i][j] ^= 255
    return res
}

Reference