My Java solution


  • 50
    H
    public class Solution {
        static boolean[][] visited;
        public boolean exist(char[][] board, String word) {
            visited = new boolean[board.length][board[0].length];
            
            for(int i = 0; i < board.length; i++){
                for(int j = 0; j < board[i].length; j++){
                    if((word.charAt(0) == board[i][j]) && search(board, word, i, j, 0)){
                        return true;
                    }
                }
            }
            
            return false;
        }
        
        private boolean search(char[][]board, String word, int i, int j, int index){
            if(index == word.length()){
                return true;
            }
            
            if(i >= board.length || i < 0 || j >= board[i].length || j < 0 || board[i][j] != word.charAt(index) || visited[i][j]){
                return false;
            }
            
            visited[i][j] = true;
            if(search(board, word, i-1, j, index+1) || 
               search(board, word, i+1, j, index+1) ||
               search(board, word, i, j-1, index+1) || 
               search(board, word, i, j+1, index+1)){
                return true;
            }
            
            visited[i][j] = false;
            return false;
        }
    }

  • 4
    S
    public class Solution {
    public boolean exist(char[][] board, String word) {
        return method(board,word);
    }
    public boolean method(char[][] board,String word){
        int row = board.length;
        int col = board[0].length;
        boolean[][] visited = new boolean[row][col];
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
                if(dfs(board,visited,i,j,0,word))
                    return true;
        return false;
    }
    public boolean dfs(char[][] board,boolean[][] visited,int row,int col,int index,String word){
        if(word.length() == index){
            return true;
        }
        if(row<0 || col<0||row>=board.length || col>=board[0].length) return false;
        char ch = word.charAt(index);
        if(!visited[row][col] && ch == board[row][col]){
            visited[row][col] = true;
            boolean res = dfs(board,visited,row-1,col,index+1,word)|| dfs(board,visited,row+1,col,index+1,word)
                   ||dfs(board,visited,row,col-1,index+1,word)|| dfs(board,visited,row,col+1,index+1,word);
            visited[row][col] = false;
            return res;
        }
        return false;
    }
    

    }


  • 0
    H
    This post is deleted!

Log in to reply
 

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