140. Word Break II

四刷 06/2022

Version #2 Bottom-up DP

感觉跟前三遍相比对这道题有了新的理解

Time - L as the length of the input string s, O(L) for the outer loop, extra O(L) to get the substring/O(L) to hash ans in the wordDict set, iterate over the previous dp result could be 2^L in the worst case

Total Time O(L*(L+2^L)) ~ O(L*2^L)

Space - O(L*2^L)

Runtime: 8 ms, faster than 29.31% of Java online submissions for Word Break II.

Memory Usage: 43.2 MB, less than 5.78% of Java online submissions for Word Break II.

class Solution {

    public List<String> wordBreak(String s, List<String> wordDict) {

        Set<String> wordSet = new HashSet<>(wordDict);

        // dp[i] - the possible sentences can be formed by substring [0, i)

        List<String>[] dp = new ArrayList[s.length() + 1];

        dp[0] = new ArrayList<>();

        dp[0].add("");

        for (int i = 1; i <= s.length(); i++) {

            dp[i] = new ArrayList<>();

            for (int j = i - 1; j >= 0; j--) {

                String sub = s.substring(j, i);

                if (!wordSet.contains(sub)) {

                    continue;

                }

                for (String prev : dp[j]) {

                    if (prev.length() > 0) {

                        dp[i].add(prev + " " + sub);

                    } else {

                        dp[i].add(sub);

                    }

                }

            }

        }

        return dp[s.length()];

    }

}

三刷
写了一个最naiive的dfs然后TLE
然后加了一个index的hashset表示当前的index以后没有可行解
pass

38.60 %
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> result = new ArrayList<>();
        dfs(s, 0, new HashSet<>(wordDict), new StringBuilder(), result, new HashSet<>());
        return result;
    }
 
    private void dfs(String s, int startIndex, Set<String> dict, StringBuilder sb, List<String> result, Set<Integer> visited) {
        if (visited.contains(startIndex)) return;
        if (startIndex == s.length()) {
            result.add(sb.substring(1).toString());
            return;
        }
        int size = result.size();
        int len = sb.length();
        for (int i = startIndex + 1; i <= s.length(); i++) {
            String temp = s.substring(startIndex, i);
            if (dict.contains(temp)) {
                sb.append(" ").append(temp);
                dfs(s, i, dict, sb, result, visited);
                if (result.size() == size) {
                    visited.add(i);
                }
                sb.setLength(len);
            }
        }
    }
}


二刷
Mem 的定义和之前写的不一样了，这次的hashmap key是startIndex
有一个问题就是只有当startIndex扫到s.length()的时候才有结果
如果扫到一般没有了就不是一个valid的结果
所以注意只有当 startIndex == s.length()的时候才创建一个base case向上返回
(1) each level we can at most have m choices
(2) each level, we have to do string concat which will cost n
(3) at most we will have height of (s / n)
based on that, total time complexity will be o(mn)^(s / n)

21.60 %
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        // dfs -> return all possible combinations of s [index, s.length())
        // loop through given result * loop through returned result of dfs
        // add result to current index and return
        if (s == null || wordDict == null) {
            return null;
        }
        Set<String> wordSet = new HashSet<>(wordDict);
        return dfs(s, wordSet, 0, new HashMap<>());
    }

    private List<String> dfs(String s, Set<String> wordSet, int startIndex,
                             Map<Integer, List<String>> map) {
        if (map.containsKey(startIndex)) {
            return map.get(startIndex);
        }
        if (startIndex == s.length()) {
            return new ArrayList<>(Arrays.asList(""));
        }
        List<String> list = new ArrayList<>();
        String curr = null;
        List<String> next = null;
        for (int i = startIndex + 1; i <= s.length(); i++) {
            curr = s.substring(startIndex, i);
            if (wordSet.contains(curr)) {
                next = dfs(s, wordSet, i, map);
                if (next != null) {
                    for (String str : next) {
                        list.add(curr + (str.equals("") ? "" : (" " + str)));
                    }
                }
            }
        }
        map.put(startIndex, list);
        return list;
    }
}


一刷
参考139和这道题
O(m^2* n)
所谓的dp就是自下向上 在知道了preSubResult的情况下，加上当前layer的信息，获得当前layer的currSubResult
而memorized dfs可以是自下向上也可是自上向下
在这道题中 用的是自下向上 call到suffix的结果后结合当前结果，向上层返回
如果是自上向下的话，一般是走到leaf以后出结果 不存在向上层返回这一步 相应的就需要加一个path variable保存上层传递下来的信息
memorized dfs
85.32 %

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) return result;
        //key - substring
        //value - all possible combinations of words in this substring
        Map<String, List<String>> map = new HashMap<>();
        List<String> baseCase = new ArrayList<>();
        baseCase.add("");
        map.put("", baseCase);
        return wordBreak(s, wordDict, map);
    }
    private List<String> wordBreak(String substr, List<String> wordDict, Map<String, List<String>> map) {
        List<String> currResult = new ArrayList<>();

        if (map.containsKey(substr)) return map.get(substr);

        List<String> subResult = null;
        for (String word : wordDict) {
            if (substr.startsWith(word)) {
                subResult = wordBreak(substr.substring(word.length()), wordDict, map);
                if (subResult.size() != 0) {
                    for (String suffix : subResult) {
                        currResult.add(suffix == "" ? word : word + " " + suffix);
                    }
                }
            }
        }
        map.put(substr, currResult);
        return currResult;
    }
}