Java DFS without extra space


  • 0

    There is no need of extra boolean visited array nor need of any kind of byte masking.
    Just need to change character to # and restore it back again before recursion ends.

    '''
    class Solution {
    public boolean exist(char[][] board, String word) {

        boolean flag = false;
        
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[i].length;j++){
                flag = flag || dfs(board, word, i, j, 0);
            }
        }
        
        return flag;
    }
    
    public boolean dfs(char[][]board, String word, int i, int j, int idx){
        
        if(i<0 || i>board.length-1 || j<0 || j>board[i].length-1)
            return false;
              
        char ch = board[i][j];
        board[i][j] = '#';
        
        if(ch != word.charAt(idx)){
            board[i][j] = ch;
            return false;
        }
        if(ch == word.charAt(idx) && idx == word.length()-1){
            board[i][j] = ch;
            return true;
        }
            
        boolean flag =      dfs(board, word, i-1,j,idx+1) ||
                            dfs(board, word, i+1,j,idx+1) ||
                            dfs(board, word, i,j-1,idx+1) ||
                            dfs(board, word, i, j+1, idx+1);
        
        board[i][j] = ch;
        return flag;
    }
    

    }
    '''


Log in to reply
 

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