LeetCode Meditations: Word Break

The description for this problem is:

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

For example:

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

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

Or:

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.

Or:

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

Also, our constraints indicate that all the strings of wordDict are **unique**, and:

• 1
• 1
• 1
• s and wordDict[i] consist of only lowercase English letters.

---

Continuing with dynamic programming solutions, we can look at a popular bottom-up approach where we build a dp array to track whether it is possible to break s into words in wordDict at each index.

Each index $i$i in the dp array will indicate whether it is possible to break the entire string into words starting at index $i$i .

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.

Let's create it with initially false values:

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

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

The last index is the empty string, which can be considered breakable, or in other words, valid:

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.

Going backwards, for each index of s, we can check if any word in wordDict can be reached from that index onwards:

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

If we're still within bounds of s (i word.length

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

If we can break it into any word in wordDict, we don't have to keep looking at other words, so we can just break out of the loop:

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

Finally, we return dp[0] — if the whole string is breakable into words in wordDict, its value will store true, otherwise false:

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

And, here is the final solution:

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



<h4>
  
  
  Time and space complexity
</h4>

<p>The time complexity is 

  <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>
 where 

  <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>
 is the string s, 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow>m </semantics></math><span><span>m</span></span></span>
</span>
 is the number of words in wordDict, and 

  <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>
 is the maximum length word in wordDict — as we have a nested loop that runs through each word in wordDict with a slice operation that uses word.length for each character in s.</p>

<p>The space complexity is 

  <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>
 because of the dp array we store for each index of s.</p>


<hr>

<p>The last dynamic programming problem in the series will be Longest Increasing Subsequence. Until then, happy coding.</p>


          

            
  

            
        

The above is the detailed content of LeetCode Meditations: Word Break. For more information, please follow other related articles on the PHP Chinese website!