Word Search - Lintcode

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.

Example

Given board =

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

Analysis:

Finding whether a path exsts is a DFS + backtracking problem. One key point is to exist from the recursion once a solution is found. in solution 1, the following lines are checked in multiple places to ensure that.

if (res){
    return;
}

in solution 2, the or operations are doing the same job.

find(board, i-1, j, word, start+1) 
|| find(board, i, j-1, word, start+1)
|| find(board, i+1, j, word, start+1)
|| find(board, i, j+1, word, start+1);

Solution 1

class Point{
    int x, y;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public boolean exist(char[][] board, String word) {
    for (int i = 0; i < board.length; i++){
        for (int j = 0; j < board[0].length; j++){
            Point p = new Point(i, j);
            helper(board, p, 0, word);
            if (res){
                return true;
            }
        }
    }

    return false;
}
int[] deltaX = new int[]{0, 0, -1, 1};
int[] deltaY = new int[]{1, -1, 0, 0};

public boolean res = false;
public void helper(char[][] board, Point p, int start, String word){    
    if (start == word.length()){
        res = true;
        return;
    }    

    if (inBound(board, p) && word.charAt(start) == board[p.x][p.y]){    
        board[p.x][p.y] = '#';
        for (int i = 0; i < deltaX.length; i++){                
            helper(board, new Point(p.x + deltaX[i], p.y + deltaY[i]), start + 1, word);
            if (res){
                return;
            }
        }
        board[p.x][p.y] = word.charAt(start);
    }
}

public boolean inBound(char[][] board, Point p){
    if (p.x < 0 || p.y < 0 || p.x >= board.length || p.y >= board[0].length){
        return false;
    }
    return true;
}

public static void main(String[] args) {
    WordSearch ws = new WordSearch();
    System.out.println(
            ws.exist(new char[][] { { 'A', 'B', 'C', 'E' }, { 'S', 'F', 'E', 'S' }, { 'A', 'D', 'E', 'E' } },
                    "ABCESEEEFS"));
}

Solution 2

public boolean exist(char[][] board, String word) {
    if(board == null || board.length == 0)
        return false;
    if(word.length() == 0)
        return true;

    for(int i = 0; i< board.length; i++){
        for(int j=0; j< board[0].length; j++){
            if(board[i][j] == word.charAt(0)){

                boolean rst = find(board, i, j, word, 0);
                if(rst)
                    return true;
            }
        }
    }
    return false;
}

private boolean find(char[][] board, int i, int j, String word, int start){
    if(start == word.length())
        return true;

    if (i < 0 || i>= board.length || 
 j < 0 || j >= board[0].length || board[i][j] != word.charAt(start)){
        return false;
     }

    board[i][j] = '#'; // should remember to mark it
    boolean rst = find(board, i-1, j, word, start+1) 
                    || find(board, i, j-1, word, start+1) 
                    || find(board, i+1, j, word, start+1) 
                    || find(board, i, j+1, word, start+1);

    board[i][j] = word.charAt(start);
    return rst;
}