题目
给定一个字符串 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 和一个字符串字典 wordDict，要求在字符串 s 中增加空格来构建句子，使得句子中所有的单词都在词典 wordDict 中。返回所有可能的句子。
解题思路：
这是一个典型的动态规划问题。我们可以使用动态规划来解决，定义 dp[i] 表示字符串 s 的前 i 个字符可以组成的句子列表。对于每个 i，我们可以从前面的某个位置 j 切割，使得 s[j:i] 是一个在词典中的单词，然后将 s[j:i] 添加到 dp[i] 中。
代码
object Solution {
def wordBreak(s: String, wordDict: List[String]): List[String] = {
val wordSet = wordDict.toSet
val n = s.length
val dp = Array.fill(n + 1)(List.empty[String])
dp(0) = List("")
for (end <- 1 to n) {
for (start <- 0 until end) {
val word = s.substring(start, end)
if (wordSet.contains(word)) {
dp(end) = dp(end) ++ dp(start).map(sentence =>
if (sentence.isEmpty) word else s"$sentence $word")
}
}
}
dp(n)
}
def main(args: Array[String]): Unit = {
val s1 = "catsanddog"
val wordDict1 = List("cat", "cats", "and", "sand", "dog")
println(wordBreak(s1, wordDict1))
// 输出 List("cat sand dog", "cats and dog")
val s2 = "pineapplepenapple"
val wordDict2 = List("apple", "pen", "applepen", "pine", "pineapple")
println(wordBreak(s2, wordDict2))
// 输出 List("pine apple pen apple", "pine applepen apple", "pineapple pen apple")
val s3 = "catsandog"
val wordDict3 = List("cats", "dog", "sand", "and", "cat")
println(wordBreak(s3, wordDict3))
// 输出 List()
}
}