Algorithm {Word Break II}

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.

First one traversing method called DFS (or BFS), second is Dynamic programming, third is some combining and tricks 🙂 to pass tests on leetcode.

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
s = "catsanddog",
dict = ["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:

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:

But, what will be if we run from other side, I mean we are storing in start bucket end indexes

But we can store in the end buckets start indexes and run loop from end to start, Hmm … good idea try to implement:
I’ve added new class for storing start index and word to improve speed of execution
Trying to run on leetcode and yeah-a, it’s accepted :))!!!

It means we solved problem.

We have used combination of DP and DFS for solve that problem, but after got Time Limit exception we have changed way of DFS running and tests passed.

That is all, Thanks.

Leave a Reply

Your email address will not be published. Required fields are marked *