Java solution,clean code, easy-understand


  • 4
    A
    public class Solution {
        public boolean exist(char[][] board, String word) {
            if(board.length == 0){
                return false;
            }
            if(board.length * board[0].length < word.length()){
                return false;
            }
            for(int i = 0; i < board.length; i++){
                for(int j = 0; j < board[0].length; j++){
                    boolean[][] check = new boolean[board.length][board[0].length];
                    if(search(board, check, word, 0, i, j)){
                        return true;
                    }
                }
            }
            return false;
        }
        
        static boolean search(char[][] board,boolean[][] check, String s, int target, int row, int col){
            if(target >= s.length()){
                return true;
            }
            if(row < 0 || col < 0 || row >= board.length || col >= board[0].length){
                return false;
            }
            if(check[row][col]){
                return false;
            }
            if(board[row][col] != s.charAt(target)){
                return false;
            }
            check[row][col] = true;
            boolean result = search(board, check, s, target + 1, row + 1, col) || search(board, check, s, target + 1, row, col + 1)
                    || search(board, check, s, target + 1, row - 1, col) || search(board, check, s, target + 1, row, col - 1);
            if(result == false){
                check[row][col] = false;
            }
            return result;
        }
    }

  • 0
    Y

    Xuncui, thank you very much for your post.
    I want to ask why you initiate check every loop since I think you could do it just once.
    Besides, Is it necessary to put the last if condition, since I think check should be set to 0 no matter the value of result.
    Sorry to bother with such stupid questions.


  • 0
    A

    Actually, that is a very good question, the check can be initialized once, I initialize it every time because this is easy understand to know that every time we begin a new search the check[][] was totally new. And I do not think we can remove the last if() in this code, the last if() make sure when temporary position do not have the word path it will be marked as false, which will not effect the next of its previous check. I suggest that you submit the code without the last if() and then you will know the reason


  • 1
    Y

    xuncui, thank you so much for your response.
    Actually I have tried to remove the last if condition around set check[row][col] to be false.
    and it strangely still passes the tests.....


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.