LeetCode: 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.

---

We can use Depth First Search to find the word. And use another board to record which element has already been visited during the traversal.

C++ Code:

/*
 * func: word_search_helper
 * goal: helper function for word search to perfrom DFS
 * @param start_i: row index
 * @param start_j: column index
 * @param check_board: check board to record which element has already been visited
 * @param word_idx: the index of char in the word
 * @param board: input char board
 * return: true or false
 */

bool word_search_helper(int start_i, int start_j, vector<vector<bool> > &check_board, int word_idx, string word, vector<vector<char> > &board){
    bool up = false, down = false, left = false, right = false;
    //If word_idx reach the boundary, we find one match
    if(word_idx == word.length()){
        return true;
    }
    
    //Go upside
    if(start_i - 1 >= 0 && board[start_i-1][start_j] == word[word_idx] && check_board[start_i-1][start_j] == false){
        check_board[start_i-1][start_j] = true;
        up = word_search_helper(start_i - 1, start_j, check_board, word_idx + 1, word, board);
        check_board[start_i-1][start_j] = false;
    }
    if(up) return true;
    
    //Go downside
    if(start_i + 1 < board.size() && board[start_i + 1][start_j] == word[word_idx] && check_board[start_i + 1][start_j] == false){
        check_board[start_i + 1][start_j] = true;
        down = word_search_helper(start_i + 1, start_j, check_board, word_idx + 1, word, board);
        check_board[start_i + 1][start_j] = false;
    }
    if(down) return true;
    
    //Go leftside
    if(start_j - 1 >= 0 && board[start_i][start_j-1] == word[word_idx] && check_board[start_i][start_j-1] == false){
        check_board[start_i][start_j-1] = true;
        left = word_search_helper(start_i, start_j-1, check_board, word_idx + 1, word, board);
        check_board[start_i][start_j-1] = false;
    }
    if(left) return true;
    
    //Go rightside
    if(start_j + 1 < board[0].size() && board[start_i][start_j + 1] ==  word[word_idx] && check_board[start_i][start_j + 1] == false){
        check_board[start_i][start_j + 1] = true;
        right = word_search_helper(start_i, start_j+1, check_board, word_idx + 1, word, board);
        check_board[start_i][start_j + 1] = false;
    }
    if(right) return true;
    
    return false;
}

/*
 * func: word_search
 * goal: to check if we can find target word in the board
 * @param board: input char board
 * @param word: target word
 * return: true or false
 */
bool word_search(vector<vector<char> > &board, string word){
    if(word.length() == 0 || board.size() ==0){
        return false;
    }
    vector<vector<bool> > check_board(board.size(), vector<bool>(board[0].size(), false));
    for(int i=0; i<board.size(); ++i){
        for(int j=0; j<board[0].size(); ++j){
            if(board[i][j] == word[0]){
                check_board[i][j] = true;
                if(word_search_helper(i, j, check_board, 1, word, board))
                    return true;
                check_board[i][j] = false;
            }
        }
    }
    return false;
}

Python Code:

# func: search the word in the char board
# @param board: input char board
# @param word: input word
# @return: True or False
def word_search(board, word):
    if not board or not word:
        return False
    check_board = [[False] * len(board[0]) for _ in xrange(len(board))]

    #Helper function to perform DFS
    def word_search_helper(start_i, start_j, curr):
        if curr == len(word):
            return True
        ret = False
        if start_i > 0 and not check_board[start_i-1][start_j] and board[start_i-1][start_j] == word[curr]:
            check_board[start_i-1][start_j] = True
            ret = word_search_helper(start_i-1, start_j, curr+1)
            check_board[start_i-1][start_j] = False
        if ret:
            return True

        if start_j > 0 and not check_board[start_i][start_j-1] and board[start_i][start_j-1] == word[curr]:
            check_board[start_i][start_j-1] = True
            ret = word_search_helper(start_i, start_j-1, curr+1)
            check_board[start_i][start_j-1] = False
        if ret:
            return True

        if start_i < len(board)-1 and not check_board[start_i+1][start_j] and board[start_i+1][start_j] == word[curr]:
            check_board[start_i+1][start_j] = True
            ret = word_search_helper(start_i+1, start_j, curr+1)
            check_board[start_i+1][start_j] = False
        if ret:
            return True

        if start_j < len(board[0])-1 and not check_board[start_i][start_j+1] and board[start_i][start_j+1] == word[curr]:
            check_board[start_i][start_j+1] = True
            ret = word_search_helper(start_i, start_j+1, curr+1)
            check_board[start_i][start_j+1] = False
        if ret:
            return True

        return False

    for i in xrange(len(board)):
        for j in xrange(len(board[0])):
            if board[i][j] == word[0]:
                check_board[i][j] = True
                if word_search_helper(i, j, 1):
                    return True
                check_board[i][j] = False

    return False