LeetCode 140 (LintCode 582) Word Break II

思路

记忆化搜索（使用记忆化的原因是有的分解形式会被重复用到），基本还是分治的思路。使用一个hashmap叫做memo来记录已经分解过的字符串及其分解形式，这样如果遇到一个新的字符串恰好在memo中，就直接返回结果而不用再搜索一遍了。
搜索过程：首先将输入字符串依次按照下标分解成两个字串s1和s2，然后检查s1是否在字典里，如果在的话就将s2交给一个“总监”，得到结果s2_res。然后将s1和该结果中的每一个可能字串进行组合（用空格隔开），加入到答案res中。最后更新memo和返回res。
【注意：需要对memo进行初始化，使用空字符串进行初始化，目的是为了防止搜索函数返回一个空list（长度=0）而不是空字符串，导致其中的判断条件出错（if(item==””)那里）】

复杂度

时间复杂度$O(n?2^n)$: n为字符串长度
空间复杂度$O(n?len(dict))$

代码

实现1

public class Solution {
    /** @param s: A string* @param wordDict: A set of words.* @return: All possible sentences.*/public List<String> wordBreak(String s, Set<String> wordDict) {
    // write your code hereMap<String, List<String>> memo = new HashMap<>();// 正确初始化，否则会导致下面的dfs返回空list而不是空字符串memo.put("", new ArrayList<>());memo.get("").add("");return dfs(s, wordDict, memo);}public List<String> dfs(String s, Set<String> wordDict, Map<String, List<String>> memo) {
    if(memo.containsKey(s)) {
    return memo.get(s);}List<String> res = new ArrayList<>();for(int i = 1; i <= s.length(); i++) {
    String s1 = s.substring(0, i);String s2 = s.substring(i);if(wordDict.contains(s1)) {
    // s2 的分解形式List<String> s2_res = dfs(s2, wordDict, memo);for(String str : s2_res) {
    if(str == "") {
    res.add(s1);} else {
    res.add(s1 + " " + str);}}}}// 在这里统一更新memo，而不是得到s2_res后就更新memo.put(s, res);return res;}
}

实现2

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
    Map<String, List<String>> memo = new HashMap<>();return helper(s, wordDict, memo);}private List<String> helper(String s, List<String> wordDict,Map<String, List<String>> memo) {
    if (memo.containsKey(s)) {
    return memo.get(s);}List<String> result = new ArrayList<>();// in case the input is "" (initial input)if (s.length() == 0) {
    return result;}//判断整个字符串是否在dict中，因为下面的for循环中如果整个字符串都在字典中，会得到空串，所以在这里判断if (wordDict.contains(s)) {
    result.add(s);}//保证切割两侧至少都有1个元素//因为如果一侧为空串的话，result为空（主要是考虑整个串都匹配的问题）for (int i = 1; i < s.length(); i++) {
    String prefix = s.substring(0, i);if (!wordDict.contains(prefix)) {
    continue;}String suffix = s.substring(i);List<String> segs = helper(suffix, wordDict, memo);for (String seg : segs) {
    result.add(prefix + " " + seg);}}memo.put(s, result);return result;}
}