Leetcode 140. Word Break II — Solution Explanation
Read the problem statement here.
Building the recursive logic step by step:
- We can only make valid partitions.
valid partitions — For the current string we break / partition the string only at those indices such that the substring from the starting index upto the partition index is present in the given dictionary wordDict.
Ex.: s = “catsanddog” and wordDict = [“cat”,“cats”,“and”,“sand”,“dog”]
- We observe from above that partitioning the string s at index 2 is valid, as because the substring “cat” is present in wordDict.
- Similarly, we also can partition the string s at index 3, as because the substring “cats” is also present in wordDict.
- It turns out that no other valid partitions can be done (except the two mentioned above).
Note: We try to make a valid partition at all the indices for the current string, the reason being we need to find out all the possible sentences.
2. Recurse on the the remaining part of the string following the same strategy as described above.
After we have successfully made a partition at index 2, we know that the substring from index 0 to 2 (i.e. “cat”) is present in wordDict. But we have got no information of the remaining part of the string from index 3 to 9 (i.e. “sanddog”).
Thus now we need to check whether the substring “sanddog” can be broken down into words which are present in wordDict. Hence we make another call to the same function, but this time we are dealing with “sanddog” substring, thus we pass the string’s starting index to be 3 (because “sanddog” starts from index 3 in the given string).
During the first function call the starting index will be 0, simply because we were considering the entire string.
3. If we make a call to our function with starting index equal to the size of the originally given string, then we are sure that we already have made valid partitions and broken down the entire string into words which are present in wordDict. This is the base case of our recursion when we have exhausted the entire string.
Let’s see how a sentence is formed for the string s = “catsanddog”
4. Whenever we get a valid word during partition we store it in some data structure and pass it to the next function call. As many times we reach the base condition, we contruct the sentence using the valid words we have got via partitioning and store the sentence in another data structure which we finally return as the result to this problem.
I hope this article helped you. Cheers !
