Leetcode 140: 单词切分II

题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
"cats and dog",
"cat sand dog"
]

示例 2：

输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。

示例 3：

输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]

思路

思路1：DP+回溯

即利用中等难度的dp单词切分获取到可能的子序列，根据是否可以整体切分以及切分标记回溯这些字序列获取最终的结果

思路2: 记忆回溯

将每个位置i记为以他为起点，到最后结果的可能切分，最后递归求解。将每个位置记为(i, list),减少无用的后缀计算，以空间换时间

思路3：DP+直接记录

将每个位置直接记录可能的前缀串，最后得到记录的全单词切分前缀串。但是在leetcode上会出现内存分配过大而超时的现象，故意需要增加判断是否可以完全完成单词切分

代码

代码1: DP+回溯

class Solution {
    public List wordBreak(String s, List wordDict) {
        List result = new LinkedList<>();
        if (s == null || s.length() == 0 || wordDict.size() == 0){
            return result;
        }
        Set hashSet = new HashSet<>(wordDict);
        boolean[] dps = new boolean[s.length() + 1];
        dps[0] = true;
        for(int end=1; end < s.length() + 1; end++){
            for(int start=0; start < end; start++) {
                if(dps[start] && hashSet.contains(s.substring(start, end))) {
                    dps[end] = true;
                    break;
                }
            }
        }
        if (!dps[s.length()]) {
            return result;
        }

        List temp = new LinkedList<>();
        wordBreakHelper(s, hashSet, s.length(), dps, temp, result);
        return result;
    }

    private void wordBreakHelper(String s, Set hashSet, int endIndex, boolean[] dps, List temp, List result) {
        if (endIndex == 0) {
            StringBuilder sb = new StringBuilder();
            for(int i = temp.size() - 1; i >= 0; i--){
                if (i != temp.size() - 1) {
                    sb.append(" ");
                }
                sb.append(temp.get(i));
            }
            result.add(sb.toString());
        }
        for(int i=endIndex - 1; i >= 0; i--) {
            if (dps[i] && hashSet.contains(s.substring(i, endIndex))){
                temp.add(s.substring(i, endIndex));
                wordBreakHelper(s, hashSet, i, dps, temp, result);
                temp.remove(temp.size() - 1);
            }
        }
    }
}

代码2: 记忆回溯

public class Solution2 {
    Map> hashMap = new HashMap<>();
    public List wordBreak(String s, List wordDict){
        List result = new LinkedList<>();
        if (s == null || s.length() == 0 || wordDict.size() == 0){
            return result;
        }
        return wordBreakHelper(s, new HashSet<>(wordDict), 0);
    }

    private List wordBreakHelper(String s, Set hashSet, int startIndex) {
        if (hashMap.containsKey(startIndex)) {
            return hashMap.get(startIndex);
        }
        List temp = new LinkedList<>();
        // 标记是否可以完全切分
        if (startIndex == s.length()) {
            temp.add("");
        }
        for(int end=startIndex+1; end <= s.length(); end++){
            if(hashSet.contains(s.substring(startIndex, end))){
                List list = wordBreakHelper(s, hashSet, end);
                for(var l: list){
                    if (l.equals("")){
                        temp.add(s.substring(startIndex, end));
                    } else{
                        temp.add(s.substring(startIndex, end) + " " + l);
                    }
                }
            }
        }
        hashMap.put(startIndex, temp);
        return temp;
    }
}

代码3: DP+直接记录

public class Solution3 {
    public List wordBreak(String s, List wordDict) {
        if (s == null || s.length() == 0 || wordDict.size() == 0 || !canWordBreak(s, wordDict)){
            return new LinkedList();
        }
        Set hashSet = new HashSet<>(wordDict);
        List[] dps = new LinkedList[s.length() + 1];
        List zero = new LinkedList<>();
        zero.add("");
        dps[0] = zero;
        for(int end=1; end <= s.length(); end++){
            List temp = new LinkedList<>();
            for(int start=0; start < end; start++){
                if (dps[start].size() > 0 && hashSet.contains(s.substring(start, end))){
                    for(var l: dps[start]){
                        temp.add(l + (l.equals("") ? "" : " ") + s.substring(start, end));
                    }
                }
            }
            dps[end] = temp;
        }
        return dps[s.length()];
    }

    public boolean canWordBreak(String s, List wordDict) {
        if (s == null || s.length() == 0) {
            return true;
        } else if(wordDict.size() == 0) {
            return false;
        }
        Set hashSet = new HashSet<>(wordDict);
        boolean[] dps = new boolean[s.length() + 1];
        dps[0] = true;

        for(int end = 1; end < s.length() + 1; end++) {
            for(int start=0; start < end; start++) {
                if (dps[start] && hashSet.contains(s.substring(start, end))) {
                    dps[end] = true;
                    break;
                }
            }
        }
        return dps[s.length()];
    }
}