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".

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.

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

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 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
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$ in the dp array will indicate whether it is possible to break the entire string into words starting at index $i$ .

Let's create it with initially false values:

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

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

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

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

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

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

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 we're still within bounds of s (i + word.length <= s.length) and we find the word (s.slice(i, i + word.length) === word), we'll mark that slot as the truth value of the "next position" that we can break the string, which will be i + word.length:

for (let i = s.length - 1; i >= 0; i--) {
  for (const word of wordDict) {
    if (i + word.length <= s.length && s.slice(i, i + word.length) === word) {
      dp[i] = dp[i + word.length];
    }
    /* ... */
  }
}

for (let i = s.length - 1; i >= 0; i--) {
  for (const word of wordDict) {
    if (i + word.length <= s.length && s.slice(i, i + word.length) === word) {
      dp[i] = dp[i + word.length];
    }
    /* ... */
  }
}

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:

for (let i = s.length - 1; i >= 0; i--) {
  for (const word of wordDict) {
    if (i + word.length <= s.length && s.slice(i, i + word.length) === word) {
      dp[i] = dp[i + word.length];
    }
    if (dp[i]) {
      break;
    }
  }
}

for (let i = s.length - 1; i >= 0; i--) {
  for (const word of wordDict) {
    if (i + word.length <= s.length && s.slice(i, i + word.length) === word) {
      dp[i] = dp[i + word.length];
    }
    if (dp[i]) {
      break;
    }
  }
}

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

function wordBreak(s: string, wordDict: string[]): boolean {
  /* ... */
  return dp[0];
}

function wordBreak(s: string, wordDict: string[]): boolean {
  /* ... */
  return dp[0];
}

And, here is the final solution:

function wordBreak(s: string, wordDict: string[]): boolean {
  let dp = Array.from({ length: s.length + 1 }, () => false); // +1 for the base case, out of bounds
  dp[s.length] = true; // base case

  for (let i = s.length - 1; i >= 0; i--) {
    for (const word of wordDict) {
      if (i + word.length <= s.length && s.slice(i, i + word.length) === word) {
        dp[i] = dp[i + word.length];
      }
      if (dp[i]) {
        break;
      }
    }
  }

  return dp[0];
}

function wordBreak(s: string, wordDict: string[]): boolean {
  let dp = Array.from({ length: s.length + 1 }, () => false); // +1 for the base case, out of bounds
  dp[s.length] = true; // base case

  for (let i = s.length - 1; i >= 0; i--) {
    for (const word of wordDict) {
      if (i + word.length <= s.length && s.slice(i, i + word.length) === word) {
        dp[i] = dp[i + word.length];
      }
      if (dp[i]) {
        break;
      }
    }
  }

  return dp[0];
}

Time and space complexity

The time complexity is $O(n * m * t)$ where $n$ is the string s, $m$ is the number of words in wordDict, and $t$ 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.

The space complexity is $O(n)$ because of the dp array we store for each index of s.

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

Eda Eren

LeetCode Meditations: Word Break

Time and space complexity