Description

LeetCode 79

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:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Analysis

This is a problem that needs us to consider about the details. First, it is easy to come up with backtracking. And I wrote the code as below.

class Solution {
    public boolean exist(char[][] board, String word) {
        if(word.length()==0) return true;
        if(board.length==0||board[0].length==0) return false;
        boolean[][] flag=new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;i++)
        {
            for(int j=0;j<board[0].length;j++)
            {
                if(exist(board,word,i,j,0,flag)) return true;
            }
        }
        return false;
    }
    public boolean exist(char[][] board,String word,int i,int j,int cur,boolean[][] flag)
    {
        if(cur==word.length()-1) return board[i][j]==word.charAt(cur);
        if(board[i][j]==word.charAt(cur))
        {
            flag[i][j]=true;
            boolean b1=false,b2=false,b3=false,b4=false;
            if(i-1>=0&&!flag[i-1][j])
                b1=exist(board,word,i-1,j,cur+1,flag);
            if(j-1>=0&&!flag[i][j-1])
                b2=exist(board,word,i,j-1,cur+1,flag);
            if(i+1<board.length&&!flag[i+1][j])
                b3=exist(board,word,i+1,j,cur+1,flag);
            if(j+1<board[0].length&&!flag[i][j+1])
                b4=exist(board,word,i,j+1,cur+1,flag);
            flag[i][j]=false;
            return b1||b2||b3||b4;
        }
        else return false;
    }
}

However, the solution is Time Limit Exceeded. I believed that if there is no other efficient method, no matter how can I change the code, the worst-case time will not be decreased. Then I looked up the solution of others, we found that the solution also uses backtracking. But it is accepted!

I felt strange. Then I looked up some blogs and found the main problem. In fact, initially, I truly directly merged the four results. But I found that I could not return it because I must implement backtracking. So I modified it to four boolean variables and merged them at last. But the leads to a bad process. No matter how good the test case is, the program will use the same worst time. Conversely, the \(Or\) operation will stop if it finds the ideal result because of its short-circuit logic. Coincidentally, one of the test case is so long but it is a nearly best case. Therefore, the correct method is to use one boolean variable to store the result that has been merged and return it after backtracking.

From this problem, we know we should not only pursue a better worst-case time, we should also try our best to decrease the best-case time.

There are two other things that could be simplified.

One is we could mask the matrix in place. The space will be decreased a lot.

The other is the corner conditions could be put at the beginning of the function. The code will be easier to read.

Solution

class Solution {
    public boolean exist(char[][] board, String word) {
        if(word.length()==0) return true;
        if(board.length==0||board[0].length==0) return false;
        for(int i=0;i<board.length;i++)
        {
            for(int j=0;j<board[0].length;j++)
            {
                if(exist(board,word,i,j,0)) return true;
            }
        }
        return false;
    }
    public boolean exist(char[][] board,String word,int i,int j,int cur)
    {
        if(cur==word.length()) return true;
        if(i<0||i>=board.length||j<0||j>=board[0].length) return false;
        if(board[i][j]==word.charAt(cur))
        {
            char c=board[i][j];
            board[i][j]='#';
            boolean res=exist(board,word,i-1,j,cur+1)||exist(board,word,i,j-1,cur+1)||exist(board,word,i+1,j,cur+1)||exist(board,word,i,j+1,cur+1);
            board[i][j]=c;
            return res;
        }
        else return false;
    }
}

Reference

[1] https://github.com/EdwardShi92/Leetcode-Solution-Code/blob/master/WordSearch.java

[2] https://blog.csdn.net/qq_38595487/article/details/81106067

Leave a Reply

Your email address will not be published. Required fields are marked *