Easy to understand classic Java DFS


  • 0
    S
    class Solution {
        int m;
        int n;
        int N;
        char[] wordArr;
        char[][] board;
        boolean[][] visited;
        public boolean exist(char[][] board, String word) {
            this.board = board;
            this.m = board.length;
            if(m < 1) return false;
            this.n = board[0].length;
            this.N = word.length();
            this.wordArr = word.toCharArray();
            this.visited = new boolean[m][n];
            
            for(int i=0; i<m; i++)
                for(int j=0; j<n; j++)
                    if(dfs(0,i,j)) return true;
            
            return false;
        }
        
        private boolean dfs(int curr, int i, int j) {
            if(curr>=N || i<0 || i>=m || j<0 || j>=n) return false;
            if(visited[i][j]) return false;
            if(board[i][j] != wordArr[curr]) return false;
            if(curr == N-1) return true;
            
            visited[i][j] = true;
            boolean result = dfs(curr+1,i,j+1) || dfs(curr+1,i,j-1) || dfs(curr+1,i+1,j) || dfs(curr+1,i-1,j);
            visited[i][j] = false;
            
            return result;
        }
    }
    

    Uses extra memory equivalent to board.


Log in to reply
 

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