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

---

Solution: Maintain a list of dictionary words for each position in the string (breakWords[0 .. s.length()]). Iterate the string from first to last position. For each position i, find the list of dictionary words that could be formed and then add it to breakWords[i + word.length()]. This algorithm is similar to the Word Break algorithm, except that in Word Break, we use an array of booleans instead of an array of list of strings.

After we find the array of list of words, gather all the results by maintaining a current list of words going from end to start in the string s and then add each result as we traverse to the beginning of the string.

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String>[] breakWords = new List[s.length() + 1];
        breakWords[s.length()] = new ArrayList<>();
        
        for (int i = 0; i < s.length(); i++) {
            if (i > 0 && breakWords[i] == null) continue;
            
            for (String word: wordDict) {
                int endIndex = i + word.length();
                if (endIndex > s.length()) continue;
                if (!word.equals(s.substring(i, endIndex))) continue;
                
                if (breakWords[endIndex] == null) {
                    breakWords[endIndex] = new ArrayList<>();
                }
                breakWords[endIndex].add(word);
            }
        }
        
        return getResults(new ArrayList<>(), breakWords, s.length(), new ArrayList<>());
    }
    
    private List<String> getResults(List<String> results, List<String>[] breakWords,
            int endIndex, List<String> list) {
        if (endIndex == 0 && list.size() > 0) {
            StringBuilder sb = new StringBuilder();
            sb.append(list.get(list.size() - 1));
            for (int i = list.size() - 2; i >= 0; i--) {
                sb.append(' ').append(list.get(i));
            }
            results.add(sb.toString());
        } else if (breakWords[endIndex] != null) {
            for (String word: breakWords[endIndex]) {
                list.add(word);
                getResults(results, breakWords, endIndex - word.length(), list);
                list.remove(list.size() - 1);
            }
        }
        return results;
    }
}