algorithm - 动态规划问题(输入不一致？)

Question

我正在尝试解决 word break LeetCode 中的问题，我不明白为什么不以相同的方式评估以下输入 - 从我的角度来看，一个为真另一个为假没有意义。谁能给我解释一下？

为什么这个输入是错误的？

"catsandog" ["cats","dog","sand","and","cat"]

这个是真的

"cars" ["car","ca","rs"]

Answer 1

因为“cars”可以分为“ca”和“rs”，它们存在于给定的字典[“car”，“ca”，“rs”]中。

另一方面，“catsandog”不能分解为所有单词都存在于 ["cats","dog","sand","and","cat"] 中。

例如，
我们可以通过以下方式破解“catsandog”:

"catsandog" ="cat"+"sand"+"og",
"catsandog"= "cats"+"and"+"og",

但是“og”不存在于给定的字典 ["cats","dog","sand","and","cat"] 中。

所以在这个问题中，如果你可以将给定的单词分解成一些单词，使得它们都存在于给定的字典中，那么你将返回 true。

但是如果给定的词典中至少不存在你的断词中的一个词，那么你将返回 false。