LeetCode 冥想：断词

此问题的描述是：

给定一个字符串 s 和一个字符串字典 wordDict，如果 s 可以分割成一个或多个字典单词的空格分隔序列，则返回 true。

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

例如：

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

或者：

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

或者：

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

此外，我们的约束表明wordDict 的所有字符串都是**唯一**，并且：

• 1
• 1
• 1
• s 和 wordDict[i] 仅由小写英文字母组成。

---

继续动态编程解决方案，我们可以看看一种流行的自下而上的方法，我们构建一个 dp 数组来跟踪是否可以在每个索引处将 s 分解为 wordDict 中的单词。

每个索引 $我$我 dp 数组中将指示是否可以将整个字符串分解为从索引开始的单词 $我$我 .

Note

dp needs to be of size s.length 1 to hold the edge case of an empty string, in other words, when we're out of bounds.

让我们用最初的错误值来创建它：

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

最后一个索引是空字符串，可以认为它是可破坏的，或者换句话说，有效的：

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

向后看，对于 s 的每个索引，我们可以检查从该索引开始是否可以到达 wordDict 中的任何单词：

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

如果我们仍在 s 的范围内 (i word.length

let dp = Array.from({ length: s.length + 1 }, () => false); // +1 for the base case, out of bounds

如果我们可以将其分解为wordDict中的任何单词，我们就不必继续查看其他单词，因此我们可以跳出循环：

dp[s.length] = true; // base case

最后，我们返回 dp[0] - 如果整个字符串可以分解为 wordDict 中的单词，则其值将存储 true，否则为 false：

for (let i = s.length - 1; i >= 0; i--) {
  for (const word of wordDict) {
    /* ... */
  }
}

而且，这是最终的解决方案：

for (let i = s.length - 1; i >= 0; i--) {
  for (const word of wordDict) {
    if (i + word.length 



<h4>
  
  
  时间和空间复杂度
</h4>

<p>时间复杂度为 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>*</mo><mi>m</mi><mo>*</mo><mi>t</mi><mo stretchy="false">）</mo></mrow>O(n * m * t) </semantics></math><span><span>O(n*</span><span>m*</span><span>t)</span></span></span>
</span>
 在哪里 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow>n </semantics></math><span><span>n</span></span></span>
</span>
 是字符串 s， 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>米</mi></mrow>米</semantics></math><span><span>米</span></span></span>
</span>
 是 wordDict 中的单词数，并且 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi></mrow>t </semantics></math><span><span>t</span></span></span>
</span>
 是 wordDict 中的最大长度单词 - 因为我们有一个嵌套循环，通过切片操作遍历 wordDict 中的每个单词，该切片操作使用 s 中每个字符的 word.length。</p>

<p>空间复杂度为 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow>O(n) </semantics></math><span><span>O(n)</span></span></span>
</span>
 因为我们为 s 的每个索引存储 dp 数组。</p>


<hr>

<p>该系列中的最后一个动态规划问题将是最长递增子序列。在那之前，祝您编码愉快。</p>


          

            
  

            
        

以上是LeetCode 冥想：断词的详细内容。更多信息请关注PHP中文网其他相关文章！