Leetcode — 79. Word Search

The link to the problem: https://leetcode.com/problems/word-search/

Given an m * n board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where “adjacent” cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Constraints:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 200
• 1 <= word.length <= 103
• board and word consists only of lowercase and uppercase English letters.

For example, 
Input: board = 
[["A","B","C","E"],
 ["S","F","C","S"],
 ["A","D","C","E"]], 
word = "ABCCCD"
Output: true 
(Path from (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,1) )

Thoughts:

Since this question seems to require us to find all the possible paths of the answers, it is nice to use backtracking to solve the problem.

The idea of using backtracking is to keep making choices and redo the previous choice once we found it is the dead-end of the current path.

Let’s see how we do backtracking for the previous example if the starting position is (0,0). (In the previous example, we will need to do backtracking at (0,0) and (2,0) because they are the only cells having the same char as the first char of the target word.)

👉Goal: Find ABCCCD in [ [A, B, C, E], [S, F, C, S], [A, D, C, E] ]

Step 1. We have decided to start at (0,0) (i.e., our first choice )
Our next choice is either go up, down, left, and right. (💡Next goal: Find BCCCD)

Step 2. Only (0,1) matches the condition. We choose to continue the path of going right. (💡Next goal: Find CCCD)

Step 3. Only (0,2) matches the condition. We choose to continue the path of going right. (💡Next goal: Find CCD)

Step 4. Only (1,2) matches the condition. We choose to continue the path of going down. (💡Next goal: Find CD)

Step 5. Although both UP (0,2) and DOWN(2,2) start with C, we will not able to choose UP because it is a traversed cell. Only (2,2) matches the condition. (💡Next goal: Find D)

Step 6. Only (2,1) matches the condition. We choose to continue the path of going left. (💡no more characters left, we’re DONE)

Below is my 9ms code that beats 29%:

public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        char firstW = word.charAt(0);
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if( board[i][j]!=firstW )
                    continue;
                if( helper( board, i, j, word.toCharArray()
                    , 0, new boolean[m][n]) )
                    return true;
            }
        }
        return false;
    }
    public boolean helper(char[][] board,int i,int j,char[] words, int indx, boolean[][] visited){
        if( indx >= words.length)
            return true;
        if( i<0 || j<0 || i>=board.length || j>=board[i].length
            ||board[i][j]!=words[indx]|| visited[i][j])
            return false;
        visited[i][j] = true; //make the choice
        if( helper(board,i+1,j,words,indx+1,visited)
           || helper(board,i,j+1,words,indx+1,visited)
           || helper(board,i-1,j,words,indx+1,visited)
           || helper(board,i,j-1,words,indx+1,visited) )
            return true;
        visited[i][j] = false; // undo the choice
        return false;
    }

📝 A little hint to improve the above code — we can actually get rid of the boolean array that records whether we visited the specific positions.

However, we still need to do something so that we won’t accidentally traverse the same cell in a path.

What we can do is temporarily update the value of the current cell, and recover the cell after traversing the possible paths.

Below is the 3ms code that beats 99%:

public boolean exist(char[][] board, String word) {
        //using backtracking to keep traversing 
        int m = board.length, n = board[0].length;
        char firstW = word.charAt(0);
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if( board[i][j]!=firstW )
                    continue;
                if( helper(board, i, j, word.toCharArray(), 0) )
                    return true;
            }
        }
        return false;
    }
    public boolean helper(char[][] board,int i,int j,char[] words, int indx){
        if( indx >= words.length)
            return true;
        if(i<0 || j<0 || i>=board.length || j>=board[i].length
           || board[i][j] != words[indx])
            return false;
        char c = board[i][j];
        board[i][j] = '.'; //temporarily modify the value
        if( helper(board,i+1,j,words,indx+1)
           || helper(board,i,j+1,words,indx+1)
           || helper(board,i-1,j,words,indx+1)
           || helper(board,i,j-1,words,indx+1) )
            return true;
        board[i][j] = c; //recover
        return false;
    }

Since we try to find any possible paths, the time complexity is exponential.