Used DFS but got a TLE


  • 3
    S
    public class Solution {
        public boolean exist(char[][] board, String word) {
            if(word == null || word.length() == 0){
                return true;
            }
            if(board == null || board.length == 0){
                return false;
            }
            boolean[][] traveled = new boolean[board.length][board[0].length];
            for(int i = 0;i<board.length;i++){
                for(int j = 0;j<board[0].length;j++){
                    if(helper(board, i,j,0,word, traveled)){
                        return true;
                    }
                }
            }
            return false;
        }
        public boolean helper(char[][] board, int row, int column, int index, String word, boolean[][] traveled){
            if(word.length() == index){
                return true;
            }
            else{
                if(row < 0 || row >= board.length || column < 0 || column >= board[0].length || traveled[row][column]){
                    return false;
                }
                if(board[row][column] == word.charAt(index)){
                    traveled[row][column] = true;
                    boolean up = helper(board, row + 1, column, index+1, word, traveled);
                    boolean down = helper(board, row - 1, column, index+1, word, traveled);
                    boolean left = helper(board, row, column - 1, index+1, word, traveled);
                    boolean right = helper(board, row, column + 1, index+1, word, traveled);
                    traveled[row][column] = false;
                    return up||down||left||right;
                }
                else{
                    return false;
                }
            }
        }
    }
    

    I think this is a quite straightforward method to the problem but got a TLE when the test input is a big 2D array with all 'a'. Please tell me where might be the problem?


  • 11
    M

    Your logic is correct. However, you are calculating the values for all possible combinations (i.e. up, down, left and right) first and then returning their logical OR. In order to optimize this you can store OR of alll recursive calls into one boolean variable.

    boolean result = helper(board, row + 1, column, index+1, word, traveled) || helper(board, row - 1, column, index+1, word, traveled) || helper(board, row, column + 1, index+1, word, traveled);
    

    Why would this work? It's because as soon as one of the conditions becomes true, "true" will be assigned to the result variable without making extra unnecessary recursive calls.

    I edited that part of your code. Here it is:

        public class Solution {
        public boolean exist(char[][] board, String word) {
            if(word == null || word.length() == 0){
                return true;
            }
            if(board == null || board.length == 0){
                return false;
            }
            boolean[][] traveled = new boolean[board.length][board[0].length];
            for(int i = 0;i<board.length;i++){
                for(int j = 0;j<board[0].length;j++){
                    if(helper(board, i,j,0,word, traveled)){
                        return true;
                    }
                }
            }
            return false;
        }
        public boolean helper(char[][] board, int row, int column, int index, String word, boolean[][] traveled){
            if(word.length() == index){
                return true;
            }
            else{
                if(row < 0 || row >= board.length || column < 0 || column >= board[0].length || traveled[row][column]){
                    return false;
                }
                if(board[row][column] == word.charAt(index)){
                    traveled[row][column] = true;
                    boolean result = helper(board, row + 1, column, index+1, word, traveled) || helper(board, row - 1, column, index+1, word, traveled) || helper(board, row, column - 1, index+1, word, traveled) || helper(board, row, column + 1, index+1, word, traveled);
                    
                    traveled[row][column] = false;
                    return result;
                }
                else{
                    return false;
                }
            }
        }
    
    }
    

  • 0
    S

    Thanks. That's a brilliant idea.


  • 0
    G

    Perfectly solve my TLE problem. Brilliant!


  • 0
    J

    I had a similar problem and still got TLE after the change. Here's my code

    class Solution {
    public:
    bool isFound(vector<vector<char>>& board, const string& word, int start, int r, int c){

        if(start == word.size() || r >= board.size() || c >= board[0].size()
            || r < 0 || c < 0 
            || board[r][c] =='*' ||  word[start] != board[r][c]){
            return false;
        }
        
        if(start == word.size() - 1) return true;
        char old_val = board[r][c];
        board[r][c] = '*';
        bool exist= isFound(board, word, start+1, c-1, r) || isFound(board, word, start+1, c+1, r) 
         || isFound(board, word, start+1, c, r-1) || isFound(board, word, start+1, c, r+1);
    
         board[r][c] = old_val;
         return exist;
                    
    }
    
    bool exist(vector<vector<char>>& board, string word) {
        int row = board.size();
        if(row == 0) return false;
        int col = board[0].size();
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(isFound(board, word, 0, i, j)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    

    };


  • 0

    @mahekjasani may I know what's the time complexity? Thanks


Log in to reply
 

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