What is the time complexity for the DFS solution?


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

    }


  • 5
    J

    I think it's O(4^length_of_word).

    The DFS solution is to search 4 directions beside the current cell.

    Imagine there's a tree, every node in this tree is a move on the board. For example:

    board = 
        [
          ['A','B','C','E'],
          ['S','F','C','S'],
          ['A','D','E','E']
        ]
    
    word = "ABCCED"
    

    The root node in the tree is board[0,0]="A", and its four children(toward 4 directions) are:

    board[0,1]="B"
    board[1,0]="S"
    board[0,-1]=no exist
    board[-1,0]=no exist
    

    So technically, this quadtree's height is L(L is length of word) and its total node number is 4^0 + 4^1 + ... + 4^L = 1/3 * ( 4^(L+1) - 1 ). So the time complexity of this dfs solution is O(4^L).

    It seems that an algorithm with O(4^n) time complexity must be TLE.

    Actually, it's true. That's why we add the visited array to memorize those visited cells in order to prune the quadtree.

    Another pruning is to cut down those illegal node, such as board[0,-1] and board[-1,0] in the example above.

    After these pruning, we get AC! \\ >0< //


  • 0
    G

    I'm a little confused here. How is that its not related to n at all? Can you explain?


  • 0
    J

    What's the meaning of n? n = length of word?


  • 0
    G

    By n i meant the length of the board (num of characters on the board).


  • 0
    J

    It of course has nothing to do with n. Because once finish searching the last letter of the word, we stop searching and return.


  • 0
    G

    I'm probably being really dumb here but visited is only for a given run (i,j). So every potential start node possible, we will go through this tree of (4^L). The dfs method is guaranteed to exit within 4^L but the exist method runs a loop too.


  • 0
    J

    Oh yes, you're right. I should consider the start nodes: O( number_of_word[0]_in_board * 4^L ). In worst case, number_of_word[0]_in_board is equal to n*m. So the worst time complexity is O(n*m * 4^L).


  • 0
    G

    Thanks for clarifying :)


  • 0
    C

    @JavaXu
    isn't O(m*n) (a polynomial) a stricter upper bound than O(4^k) (exponential)?

    If so, isn't the answer supposed to be O(mn * mn) instead of O(m*n * 4^k)?


  • 0
    E

    @cheyuanl
    I guess it should be the smaller one of the two?


Log in to reply
 

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