喵酱: Word Break II @leetcode

喵酱: Word Break II @leetcode

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"].

This is a very typical problem of combination of back tracking and DP.

Basic idea is, we start from first letter in string S, then we check every substr we have so far to see if it's in dict.
If it's in dict, then we go iteratively to search the rest substr to find out all combinations. However, it will lead to redundant
searching during the iteration. Thus we can use an array to record the search result to avoid repeated searching.

We define res[i+1] = true, means substr(i,n) has combination in dict, otherwise it doesn't.

Read full article from 喵酱: Word Break II @leetcode