LeetCode Meditations: Word Break

The description for 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

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

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) {

    /* ... */

  }

}

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];

    }

    /* ... */

  }

}

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;

    }

  }

}

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];

}

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];

}

Time and space complexity

The time complexity is

$O(n\ast m\ast 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.