Complexity of DFS + DP solution?


  • 0
    R

    What is the complexity of the solution please?


  • 0
    L

    DP is O(n^3), three for loops to store information. DFS to find all solution may depend on number of correct breaking candidates we have, where the min is 0, maximum is O(2^n) (for all possible combination numbers). Usually we can assume there will be a constant number of potential breaking given a normal dataset, like <1M possible combination given a string with length <=100.


  • 0
    R

    Thank you. I think you meant to say "DP is O(n^2)".


Log in to reply
 

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