Word Break II


  • 0

    Click here to see the full article post


  • 2
    J

    Why DP is time limited?


  • 0
    Y

    Where to get the tutorial about DP


  • 1
    M

    Why is DP method Time Limit Exceeded while it is still O(n3)?


  • 0
    Y

    For the recursive approach, why add "" if (start == s.length())?


  • 0
    Y

    For the recursive approach, why add "" if (start == s.length())? nvm, I got it.


  • 2
    S

    I can't agree with the complexity analysis of the brute force search. You can think the brute force search is to try all the options whether to insert a space at position i.
    So the total options to search is 2^n, so the time complexity should be O(2^n) n is the length of the sentence to break

    same thing, for the space complexity, it's same all those 2^n can be a valid break, so the space complexity is also O(2^n)


  • 0
    K

    @vinod23

    Can you help to write code in iterative manner for Approach #2 Recursion with memoization [Accepted] ?


  • 0
    K

    This problem is quite frustrating. Why is it that if the input is:
    "abcd"
    ["a","abc","b","cd"]
    Expected:
    ["a b cd"]

    but if the input is:
    "a"
    ["a"]
    Expected:
    ["a"]
    ?

    Why isn't "abc" an acceptable sentence in the first test case?


  • 0
    C

    I don't really agree that the time complexity of approach 2 is O(n^3). Considering the worst case string = "aaaaaaa" and every prefix of the string is in the dictionary, the list of string the algorithm desires is basically generating all combinations of the space existence between any two characters. So it is at least O(2^n) because you need at least 2^n strings in the result list.


Log in to reply
 

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