Time limit exceeded in DFS solution


  • 0
    V

    public class Solution {

    public boolean exist(char[][] board, String word) {
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(dfs(board, word, i, j, 0)) return true; 
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] board, String word, int row, int col, int currIndex){
        if(currIndex >= word.length()) return true;
        
        if(row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] != word.charAt(currIndex)){
            return false;
        }
        char temp = board[row][col];
        board[row][col] = '#'; // make it visited
        boolean res = (dfs(board, word, col -1, row, currIndex+1) || 
                dfs(board, word, col +1, row, currIndex+1) || 
                dfs(board, word, col , row -1, currIndex+1) || 
                dfs(board, word, col , row +1, currIndex+1));
        board[row][col] = temp;
        return res;
    }
    

    }


  • 0
    V

    any help please!


  • 0
    V

    found the mistake. sorry to ask.


  • 0
    K

    'Coz you did not record which cells has already been traversed. Thus the indexes can go back and forth and it will never ends.


Log in to reply
 

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