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.

Have you met this question in a real interview?

Yes

Example

Gieve s =lintcode,
dict =["de", "ding", "co", "code", "lint"].

A solution is["lint code", "lint co de"].

This problem is a classical search problem. kind of similar to Palindrome Partition in terms of search (cutting strings), but if just do a standard dfs, it will fail on TLE. so we need to use a little dp to cut the paths of the search. in this way, it is kind of similar to word ladder II where we have to remember the distance from a point between start and end to the end, and we will use this to guide the search to only move along the shortest path. in this case we will use dp to provide from a index if we proceed whether it is possible to construct a sentence. so the function is f[i] = f[j + 1] && wordDict.contains(s.substring(i, j + 1) where f(i) represents the possiblity of starting from i whether it is possible to form at least 1 sentence. note is from i to the end. cuz this will like the distance in word ladder to help us to skip that paths if it is not possible to move forward

public class Solution {
    /**
     * @param s a string
     * @param wordDict a set of words
     */
    public List<String> wordBreak(String s, Set<String> wordDict) {
        // Write your code here
        List<String> ans = new ArrayList<>();
        if (wordDict == null || wordDict.size() == 0) {
            return ans;
        }

        //use dp to remember from i to j whether a sentence is possible
        boolean[] dp = getPossible(s, wordDict);

        String tempString = "";
        //dfs search the results
        dfsWordBreak(ans, tempString, dp, wordDict, s, 0);

        return ans;
    }


    //f(i, j) = f(j + 1) && dict.contains(s.substring(i, j + 1))
    public boolean[] getPossible(String s, Set<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[s.length()] = true;
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (dp[j + 1] && wordDict.contains(s.substring(i, j + 1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp;
    }


    //dfs
    public void dfsWordBreak(List<String> ans,
                             String tempString,
                             boolean[] dp,
                             Set<String> wordDict,
                             String s,
                             int startIndex) 
                             {
        if (startIndex >= s.length()) {
            ans.add(tempString.trim());
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            String curWord = s.substring(startIndex, i + 1);
            if (!dp[i + 1] || !wordDict.contains(curWord)) {
                continue;
            }

            tempString += curWord + " ";
            dfsWordBreak(ans, tempString, dp, wordDict, s, i + 1);
            tempString = tempString.trim();
            tempString = tempString.substring(0, tempString.lastIndexOf(" ") + 1);
        }
    }
}