Word Search

Question (LC.79)

Given a 2D board and a target word, check if the target word is in the board.

Edges are horizontal and vertical

Example

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

(board, "ABFD") => true
(board, "SEE") => true
(board, "ABFA") => false

Approach

We want to find a valid path. BFS is designed for layer search. Path search is DFS's job.

DFS Code

public boolean exist(char[][] board, String query) {
    int m = board.length;
    int n = board[0].length;
    boolean[][] visited = new boolean[m][n];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (dfsWord(board, visited, query, 0, new Pos(i,j)))
                return true;
    return false;
}

// dfs on suffix
private boolean dfsWord(char[][] board, 
                        boolean[][] visited, 
                        String query,
                        int charPos,
                        Pos current) {
    // base case 1. out of bound 2. does not match char 3. visited 4. full match
    if (!inBound(board, current)) return false;
    if (visited[current.row][current.col]) return false;
    if (board[current.row][current.col] != query.charAt(charPos)) return false;
    if (charPos == query.length() - 1) return true;
    // previsit
    visited[current.row][current.col] = true;
    // dfs try all paths
    for (int p = 0; p < 4; p++) {
        Pos neighbor = new Pos(current.row + drow[p], current.col + dcol[p]);
        if (dfsWord(board, visited, query, charPos + 1, neighbor)) {
            return true;
        }
    }
    // postvisit
    visited[current.row][current.col] = false;
    return false; // all paths failed
}

Time Complexity

The worst case is an exhaustive search so exponential time. O(4^len(word)).

Word Search II (LC.212)

Use a trie to accelerate the prefix search