LeetCode 140. Word Break II

word-break-ii.java

/**
 * https://leetcode.com/problems/word-break-ii/
 *
 * O(n * m) + O(n * num) runtime, O(n) space
 *   where n is the length of the string
 *     m is the length of the longest string in the dictionary
 *     num is the number of solutions
 *
 * use DP and DFS to solve this question with the solution of 139. Word Break
 *
 * still, note that use Set's contains() instead of String's equals() to compare strings to reduce the runtime
 */

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        LinkedList<Integer>[] cache = new LinkedList[s.length() + 1]; // note new LinkedList[s.length() + 1] here
        // new LinkedList<Integer>[s.length() + 1] and new LinkedList<>[s.length() + 1] are not allowed
        
        // initialization
        cache[0] = new LinkedList<Integer>();
        cache[0].add(-1);
        int maxLen = getMaxLength(wordDict);
        for (int i = 1; i <= s.length(); i++) {
            for (int len = maxLen; len >= 1; len--) {
                if (i - len >= 0 && cache[i-len] != null && wordDict.contains(s.substring(i - len, i))) {
                    if (cache[i] == null) {
                        cache[i] = new LinkedList<Integer>();
                    }
                    cache[i].add(i - len);
                }
            }
        }
        LinkedList<String> res = new LinkedList<>();
        if (cache[s.length()] == null) { // note that it could be null
            return res;
        }
        for (int n : cache[s.length()]) {
            dfs(n, s.length(), "", s, cache, res);
        }
        return res;
    }
    
    private int getMaxLength(Set<String> wordDict) {
        int ans = 0;
        for (String str : wordDict) {
            ans = Math.max(ans, str.length());
        }
        return ans;
    }
    
    // use DFS (backtracking) to get the result
    private void dfs(int start, int end, String str, String s, List<Integer>[] cache, LinkedList<String> res) {
        if (start == -1) {
            res.add(str.substring(1));
        } else {
            for (int n : cache[start]) {
                dfs(n, start, " " + s.substring(start, end) + str, s, cache, res);
            }
        }
    }
}