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 =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

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

10/2/2015 update

The previous solution is quite violent. It used a marker ‘\0’ to mark a cell as visited. In this newer solution, I allocate a hashtable to store the visited map.

It is imported to retrieve the spot before return from current node.

erase first char in word
add current cell to visited hashmap
//do some work, go deeper

insert the erased char to the beginning of word
remove current cell from visited hashmap

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        unordered_map<int, int> visited;
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                if(DFS(board, word, visited, i, j)){
                    return true;
                }
            }
        }
        return false;
    }
    bool DFS(vector<vector<char> >& board, string& word, unordered_map<int, int>&visited, int r, int c){
        //base condition
        if(word.size() == 0) return true;
        
        //out of boundary
        if(r < 0 || r >= board.size() || c < 0 || c >= board[0].size()){
            return false;
        }
        
        //visited or not
        if(visited.find(r * board[0].size() + c) != visited.end()) return false;
        
        //not match
        if(board[r][c] != word[0]) return false;
        
        //board[r][c] == word[0]
        word.erase(0, 1);
        visited[r * board[0].size() + c] = 1;
        
        int dict[][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        for(int k = 0; k < 4; k++){
            int nr = r + dict[k][0];
            int nc = c + dict[k][1];
            if(DFS(board, word, visited, nr, nc)){
                return true;
            }
        }
        visited.erase(r * board[0].size() + c);
        word.insert(0, 1, board[r][c]);
        return false;
    }
};

直接深搜DFS。常规题。

class Solution {
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(_exist(board, word, i, j) == true){
                    return true;
                }
            }
        }
        return false;
    }
    bool _exist(vector<vector<char>> &board, string word, int r, int c){
        if(word.empty()){
            return true;
        }
        if(r < 0 || r >= board.size() || c < 0 || c >= board[0].size()){
            return false;
        }
        if(board[r][c] != word[0]){
            return false;
        }
        else{//board[r][c] == word[0]
            char tmp = board[r][c];
            board[r][c] = '\0'; //mark as visited, but if a valid result is found, it will 
            word.erase(0, 1);
            for(int i = -1; i <= 1; i += 2){
                if(_exist(board, word, r + i, c) == true){
                    return true;
                }
            }
            for(int j = -1; j <= 1; j += 2){
                if(_exist(board, word, r, c + j) == true){
                    return true;
                }       
            }
            board[r][c] = tmp;
            return false;
        }
    }
};