140. Word Break II

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Example 2:

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []

Code

class Solution {
    HashMap<Integer, List<String>> map = new HashMap<>();

    public List<String> wordBreak(String s, List<String> wordDict) {
        HashSet<String> wordDictSet = new HashSet<>(wordDict);
        return dfs(s, wordDictSet, 0);
    }

    private List<String> dfs(String s, HashSet<String> dict, int start) {
        if (map.containsKey(start)) {
            return map.get(start);
        }

        List<String> res = new ArrayList<>();

        if (start == s.length()) {
            res.add("#");
            return res;
        }

        for (int i = start + 1; i <= s.length(); i++) {
            String curr = s.substring(start, i);
            if (dict.contains(curr)) {
                List<String> list = dfs(s, dict, i);
                for (String temp : list) {
                    if (temp == "#") {
                        res.add(curr);
                    } else {
                        res.add(curr + " " + temp);
                    }
                }
            }
        }

        map.put(start, res);

        return res;
    }
}

In the worst case the runtime of this algorithm is O(2^n).

Consider the input “aaaaaa”, with wordDict = [“a”, “aa”, “aaa”, “aaaa”, “aaaaa”, “aaaaa”]. Every possible partition is a valid sentence, and there are 2^n-1 such partitions. It should be clear that the algorithm cannot do better than this since it generates all valid sentences. The cost of iterating over cached results will be exponential, as every possible partition will be cached, resulting in the same runtime as regular backtracking. Likewise, the space complexity will also be O(2^n) for the same reason - every partition is stored in memory.

Time complexity: O(2^n)

Space complexity: O(2^n)