Java 11ms easy to understand solution using backtracking


  • 0
    T
    public class Solution {
       public boolean exist(char[][] board, String word) {
            if(board.length == 0 || board[0].length== 0) return false;
            
            int lenv = board.length;
            int lenh = board[0].length;
            for(int i=0; i<lenv; i++)
                for(int j=0; j<lenh; j++)
                    if(backTrack(board, i, j, lenv, lenh, word, 0)) return true;
            return false;
        }
        private boolean backTrack(char[][] board, int i, int j, int lenv, int lenh, String word, int exp){
            if(word.charAt(exp) != board[i][j]) return false;
            if(exp == word.length()-1) return true;
            // Modify the current char so that it won't be visited again.
            char bak = board[i][j];
            board[i][j] = '0';
            // Search every possible neighbor
            if(i-1>=0 && board[i-1][j]!='0' && backTrack(board, i-1, j, lenv, lenh, word, exp+1)) return true;
            if(i+1<lenv && board[i+1][j]!='0' && backTrack(board, i+1, j, lenv, lenh, word, exp+1)) return true;
            if(j-1>=0 && board[i][j-1]!='0' && backTrack(board, i, j-1, lenv, lenh, word, exp+1)) return true;
            if(j+1<lenh && board[i][j+1]!='0' && backTrack(board, i, j+1, lenv, lenh, word, exp+1)) return true;
            board[i][j] = bak;
            return false;
        }
    }
    

Log in to reply
 

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