Today we will work on hard task Word Break II. Why this task is hard? I can say, here, during resolving this problem, you will and you should use a few techniques.
OK, try to read task description :
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
["cat", "cats", "and", "sand", "dog"].
A solution is
["cats and dog", "cat sand dog"].
We can see, that we have some dictionary and first idea will be about traversing through dictionary, but it will be mistake. For example you have simple input string like catsanddog and dictionary with 1 billion of words, what is the complexity will be ? Yes, O(N^2) where is N equals to 1 billion. And generally I do not think that complexity of our solution should be dependent from dictionary size!
What we can todo, try to analyse … We can run through all letters in input word and try to find all words from our dic, if found put to storage (DP) end index of word (or start index) depend to the direction of string traversing. I am storing not just indexes but word too, to speed up our solution.
OK, at the end you will have something like that:
[crayon-5bc5b003d0c6d199194491/] But you will get Time Limit Exceeded exception. Generally this solution is good, but we have problems in analysing words like that :
So, how to fix that problem, you can see our algorithm run from start to end and check if the counts of words equals to input word size, it means we have used all letters from input word:
[crayon-5bc5b003d0c7c075046808/] But, what will be if we run from other side, I mean we are storing in start bucket end indexes
[crayon-5bc5b003d0c83204684123/] I’ve added new class for storing start index and word to improve speed of execution
[crayon-5bc5b003d0c87795450271/] Trying to run on leetcode and yeah-a, it’s accepted :))!!!
It means we solved problem.
That is all, Thanks.