LeetCode题练习与总结：单词拆分Ⅱ--140

一、题目描述

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。

注意：词典中的同一个单词可能在分段中被重复使用多次。

示例 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 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中所有字符串都不同

二、解题思路

这个问题是一个典型的动态规划问题，可以使用回溯法来解决。解题思路如下：

动态规划预处理：首先，我们可以用动态规划的方法预处理字符串s，创建一个布尔数组dp，其中dp[i]表示s中前i个字符组成的字符串是否可以被空格拆分为一个或多个在字典中出现的单词。这样我们可以快速判断一个子串是否可被分割。
回溯法搜索：然后，我们使用回溯法来找出所有可能的句子。我们从字符串的开始进行，对于每一个位置，我们尝试用字典中的单词进行匹配，如果匹配成功，则将这个单词加入到当前的句子中，并递归地尝试匹配后续的字符串。当递归到达字符串末尾时，我们就找到了一个有效的句子。
去重：由于字典中可能存在重复的单词，我们需要确保在回溯的过程中不会产生重复的句子。

三、具体代码

import java.util.*;

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        // 预处理，使用set提高查找效率
        Set<String> wordSet = new HashSet<>(wordDict);
        // dp[i] 表示s的前i个字符是否可以由字典中的单词组成
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        
        // 动态规划填表
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        // 如果整个字符串都不能拆分，直接返回空列表
        if (!dp[s.length()]) {
            return new ArrayList<>();
        }
        
        // 使用回溯法找出所有可能的句子
        List<String> sentences = new ArrayList<>();
        backtrack(s, wordSet, dp, 0, new StringBuilder(), sentences);
        return sentences;
    }
    
    private void backtrack(String s, Set<String> wordSet, boolean[] dp, int start, StringBuilder sentence, List<String> sentences) {
        if (start == s.length()) {
            sentences.add(sentence.toString().trim());
            return;
        }
        
        for (int end = start + 1; end <= s.length(); end++) {
            if (dp[end] && wordSet.contains(s.substring(start, end))) {
                int prevLength = sentence.length();
                sentence.append(s, start, end).append(" ");
                backtrack(s, wordSet, dp, end, sentence, sentences);
                sentence.setLength(prevLength); // 回溯
            }
        }
    }
    
    // 测试代码
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> wordDict = Arrays.asList("cat", "cats", "and", "sand", "dog");
        System.out.println(solution.wordBreak("catsanddog", wordDict));
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

动态规划填表：对于字符串s的每个位置i，我们可能需要检查从0到i-1的所有位置j，以确定是否存在一个单词可以匹配s[j:i]。因此，动态规划的时间复杂度为O(n^2)，其中n是字符串s的长度。
回溯法搜索：在最坏的情况下，我们可能需要生成所有可能的句子，每个句子都是由字典中的单词组成的。如果字典中有m个单词，那么最坏情况下的时间复杂度为O(m^n)，因为每个位置都可能尝试字典中的每个单词。