Coding Interview Questions | Word Break

January 30th, 2024

Word Break Problem Introduction:

This summary will talk about my solution to the word break problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

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.

How do you solve the Word Break Problem using Dynamic Programming?

Solution:

function wordBreak(s: string, wordDict: string[]): boolean {
  const n = s.length;
  const dp: boolean[] = new Array(n).fill(false);

  for (let i = 0; i < n; i++) {
    for (let word of wordDict) {
      const wordLen = word.length;

      if (
        i - wordLen + 1 >= 0 &&
        s.substring(i - wordLen + 1, i + 1) === word
      ) {
        if (i - wordLen === -1 || dp[i - wordLen]) {
          dp[i] = true;
          break;
        }
      }
    }
  }

  return dp[n - 1];
}

Word Break Solution Summary:

Below is a detailed breakdown of the key aspects of the provided solution for the “Word Break” problem seen above:

Approach:

1. Dynamic Programming Array:

   • We use a dynamic programming array dp, where dp[i] indicates whether the substring s[0...i] can be segmented into valid words.
   • dp[i] is true if s[0...i] is a valid word or if it can be formed by combining multiple words from the dictionary.

2. Iterative Process:

   • We iterate through each character of the input string s.
   • For each character at index i, we iterate through the words in the dictionary.
   • We check if the substring ending at index i matches any word in the dictionary.
   • If a match is found, we check whether the substring before the matched word (if any) is also a valid word (determined by dp[i - wordLen]).

3. Updating dp Array:

   • If a match is found for a word, and the substring before it is valid or it’s the start of the string, we set dp[i] to true.
   • This means that the substring up to index i can be segmented into valid words.

4. Final Result:

   • The final result is obtained from dp[n-1], where n is the length of the input string.
   • If dp[n-1] is true, it means the entire string can be segmented into valid words.

Example:

Let’s take the example where s = "catsandog" and wordDict = ["cats", "dog", "sand", "and", "cat"].

1. Initialization:

   • Initialize dp array with false.
   • For dp[0], we check if "c" is a valid word, which is false.
   • Repeat this process for each character in the string.

2. Iteration:

   • When we reach the character "s" at index 3, we find a match with the word "cats".
   • We check if the substring before “cats” is valid, and it is (dp[3 - 4] is dp[-1] which is considered true).
   • So, we set dp[3] to true.
   • This process continues for other words and characters.

3. Final Result:

   • The final result is obtained from dp[10], and it is false.

Time Complexity:

The time complexity is O(n * m), where n is the length of the input string and m is the number of words in the dictionary. This is because, for each character, we iterate through the dictionary.

Space Complexity:

The space complexity is O(n) for the dynamic programming array.