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++){
            // 当前范围是不是一个word
            if(dict.contains(s.substring(start, i))){
                // 把后边的组合求出来
                // 把当前的word加到后边的组合前边
                List<String> list = dfs(s, dict, i);
                for(String temp : list){
                    // 最后一个不加空格
                    res.add(s.substring(start, i) + (temp == "" ? "" : " ") + 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)