140. 单词拆分 II

🔴   🔖  字典树 记忆化搜索 数组 哈希表 字符串 动态规划 回溯  🔗 力扣 LeetCode

题目

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: []

Constraints:

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 10
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.
• Input is generated in a way that the length of the answer doesn't exceed 105.

题目大意

给定一个字符串 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 中所有字符串都 不同

解题思路

可以使用 动态规划（Dynamic Programming） 来解决这个问题。

1. 定义状态：

   • 定义一个数组 dp[i]，表示字符串 s[0:i] 的所有可能的有效分割结果。
   • 例如：dp[5] 表示 s[0:5] 的所有有效分割结果。

2. 转移方程：

   • 遍历字符串的每一个右边界 right，尝试用 left 分割成两部分：
     • 左部分 s[0:left] 的分割结果保存在 dp[left] 中。
     • 右部分 s[left:right]（称为 suffix）是否在 wordDict 中。
   • 如果 suffix 是字典中的单词，将它与 dp[left] 中的每一个分割结果拼接起来，构成新的分割结果，存入 dp[right]。

3. 初始化：

   • dp[0] = ['']，表示空字符串的分割结果。

4. 最终答案：

   • dp[n]，即字符串 s[0:n] 的所有分割结果。

具体算法如下：

1. 将 wordDict 转换成一个 Set，便于快速判断单词是否在字典中。
2. 初始化一个长度为 n+1 的二维数组 dp，每个位置存储该子字符串的所有可能分割结果。
3. 遍历 right 从 1 到 n，对于每个 right：
   • 遍历 left 从 0 到 right，计算子串 s[left:right]；
   • 如果 s[left:right] 在字典中，取出 dp[left] 的所有分割结果，并将其与当前子串拼接，存入 dp[right]。
4. 最后返回 dp[n]，即完整字符串的所有可能分割结果。

复杂度分析

• 时间复杂度： O(n^2 + m * L)

  • 遍历所有子串：外层循环 O(n)，内层循环 O(n)，子串判断 O(1)。
  • 拼接字符串结果：假设最终有 m 个有效分割，每次拼接代价为 O(L)（平均单词长度为 L）。
  • 综合时间复杂度为：O(n^2 + m * L)。

• 空间复杂度： O(n * m + k)

  • 动态规划数组 dp 需要存储结果，最坏情况下存储所有分割结果，空间复杂度为 O(n * m)。
  • 字典 wordSet 的空间为 O(k)，其中 k 为字典单词总数。

代码

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {string[]}
 */
var wordBreak = function (s, wordDict) {
	const n = s.length; // 字符串长度
	const wordSet = new Set(wordDict); // 用 Set 存储字典，方便快速查找

	// 初始化 dp 数组，dp[i] 表示 s[0:i] 的所有分割结果
	let dp = new Array(n + 1).fill().map(() => []);
	dp[0] = ['']; // 空字符串的分割结果是一个空字符串

	// 遍历字符串的右边界
	for (let right = 1; right <= n; right++) {
		let temp = []; // 存储 dp[right] 的分割结果

		// 遍历左边界，寻找有效的分割点
		for (let left = 0; left < right; left++) {
			const suffix = s.slice(left, right); // 子串 s[left:right]

			// 如果后缀是字典中的单词
			if (wordSet.has(suffix)) {
				// 将 dp[left] 中的每个分割结果拼接后缀
				for (let substring of dp[left]) {
					temp.push(`${substring}${substring ? ' ' : ''}${suffix}`);
				}
			}
		}

		dp[right] = temp; // 更新 dp[right]
	}

	return dp[n]; // 返回 s[0:n] 的所有分割结果
};

相关题目

题号	标题	题解	标签	难度	力扣
139	单词拆分	[✓]	字典树 记忆化搜索 数组 3+	🟠	🀄️ 🔗
472	连接词		深度优先搜索 字典树 数组 2+	🔴	🀄️ 🔗