leetcode: Word Break II

问题描述：

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

原问题链接：https://leetcode.com/problems/word-break-ii/

 

问题分析

　　关于这个问题的递归推导关系实际上和前一个问题是一样的。对于长度i的字符串来说，它包含的字符串的划分等于所有wordBreak(s.substring(0, j)) + s.substring(j, i)(j >= 0 j < i)。这样，在这个问题里，我们需要在对应s的每个位置设置一个对应的List<String>，这样当后面碰到一个匹配的情况下，我们就将第j个位置的list里的每个元素，和s.substring(j, i)串起来加入到新的列表中。这个新的列表就构成了i位置的列表。

　　于是我们就有了第一种方法。

 

动态规划法

　　有了前面的讨论，我们需要在每个位置建立对应的List<String>，因此在实现的时候可以采用一个Map<Integer, List<String>> map。key表示s里面每个索引的值，value表示每个索引位置对应的list。剩下的就是我们采用类似的两层遍历，建立这个列表。

　　有了之前的讨论，我们得到的代码如下：

 

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        Map<Integer, List<String>> map = new HashMap<>();
        List<String> l = new ArrayList<>();
        l.add("");
        map.put(0, l);
        for(int i = 1; i <= s.length(); i++) {
            List<String> values = new LinkedList<>();
            for(int j = 0; j < i; j++) {
                if(wordDict.contains(s.substring(j, i))) {
                    for(String word: map.get(j)) {
                        values.add((word.isEmpty() ? "" : (word + " ")) + s.substring(j, i));
                    }
                }
            }
            map.put(i, values);
        }
        return map.get(s.length());
    }
}

　　这部分代码的时间复杂度达到了O(n ^ 3) 。虽然结果是正确的，但是在字符串比较长的时候容易超时。

 

改进

　　我们看前面的方法，它在元素长度比较长而且有很多重复的情况下，会出现有很多的匹配，而这里针对每个匹配，它要在不同的索引下面建立新的列表并且拷贝添加元素进去。这样会消耗大量的时间。而对于之前的情况它的根源在于有很多重复的子串，我们完全可以跳过这些子串去重用它们，而不是每次要构建一个索引位置的串。这些不同索引位置的串中间出现的大量重复才是关键点。

　　于是，我们可以考虑不是针对索引位置建立列表，而是针对不同的串来建立列表。这样当有重复的子串是，我们根据串所对应的列表来加入对应的元素就可以了。这样节约了一个个拷贝的时间。

　　从实现的细节来说，我们可以定义一个全局的Map<String, List<String>>  map。这里记录某个长度的串所对应的划分。我们从字符串索引１的位置开始，每次判断s.substring(0, i)，如果dict包含有这个串，则递归的将当前子串和wordBreak(s.substring(i), dict)的结果加入到当前列表中。当然，我们在函数中会判断map中或者dict中是否已经包含有当前串s了，如果有，就直接返回。

　　详细的代码实现如下：

 

public class Solution {
    Map<String, List<String>> mem = new HashMap<>();
    public List<String> wordBreak(String s, Set<String> dict) {
        if (mem.get(s) != null) return mem.get(s);
        List<String> result = new ArrayList<>();
        if (dict.contains(s)) result.add(s);
        for (int i = 1; i < s.length(); i++) {
            String word = s.substring(0, i);
            if (dict.contains(word)) {
                List<String> tmp = wordBreak(s.substring(i), dict);
                for (String str : tmp) {
                    result.add(word + " " + str);
                }
            }
        }
        mem.put(s, result);
        return result;
    }
}