Click here to see the full article post
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)
Can you help to write code in iterative manner for Approach #2 Recursion with memoization [Accepted] ?
This problem is quite frustrating. Why is it that if the input is:
["a b cd"]
but if the input is:
Why isn't "abc" an acceptable sentence in the first test case?
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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.