SimuVedaAlgorithms Lab Open in the lab

Dynamic programming / Intermediate

Word Break Visualizer

dp[i] says whether the first i letters can be built from words. dp[0] is true (the empty start). dp[i] is true if some earlier dp[j] is true and the letters from j to i form a word.

Start the Word Break simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n²)
Average timeO(n²)
Worst timeO(n²)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. dp[0] = T: an empty prefix needs no words. Column i stands for the first i letters.
  2. dp[0] is T, but "a" is not a word.
  3. No split works for the first 1 letters: dp[1] stays F.
  4. dp[0] is T, but "ap" is not a word.
  5. No split works for the first 2 letters: dp[2] stays F.
  6. dp[0] is T, but "app" is not a word.
  7. No split works for the first 3 letters: dp[3] stays F.
  8. dp[0] is T, but "appl" is not a word.
  9. No split works for the first 4 letters: dp[4] stays F.
  10. dp[0] is T and "apple" is a word, so dp[5] = T.
  11. dp[0] is T, but "applep" is not a word.
  12. dp[5] is T, but "p" is not a word.
  13. No split works for the first 6 letters: dp[6] stays F.
  14. dp[0] is T, but "applepe" is not a word.
  15. dp[5] is T, but "pe" is not a word.
  16. No split works for the first 7 letters: dp[7] stays F.
  17. dp[0] is T, but "applepen" is not a word.
  18. dp[5] is T and "pen" is a word, so dp[8] = T.
  19. dp[0] is T, but "applepena" is not a word.
  20. dp[5] is T, but "pena" is not a word.
  21. … 14 more steps …
  22. dp[0] is T, but "applepenapple" is not a word.
  23. dp[5] is T, but "penapple" is not a word.
  24. dp[8] is T and "apple" is a word, so dp[13] = T.
  25. dp[13] = T: "applepenapple" = apple + pen + apple.

Try it with your own input →

Word break in Java, Python, C++, C and JavaScript

boolean wordBreak(String s, Set<String> dict) {
  boolean[] dp = new boolean[s.length() + 1];
  dp[0] = true;
  for (int i = 1; i <= s.length(); i++)
    for (int j = 0; j < i; j++)
      if (dp[j] && dict.contains(s.substring(j, i))) {
        dp[i] = true; break;
      }
  return dp[s.length()];
}
def word_break(s, words):
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[len(s)]
bool wordBreak(const string& s, const unordered_set<string>& dict) {
  vector<bool> dp(s.size() + 1, false);
  dp[0] = true;
  for (size_t i = 1; i <= s.size(); i++)
    for (size_t j = 0; j < i; j++)
      if (dp[j] && dict.count(s.substr(j, i - j))) {
        dp[i] = true; break;
      }
  return dp[s.size()];
}
#include <string.h>

int inDict(const char* s, int len, const char* dict[], int nd) {
  for (int k = 0; k < nd; k++)
    if ((int)strlen(dict[k]) == len && strncmp(s, dict[k], len) == 0) return 1;
  return 0;
}
int wordBreak(const char* s, const char* dict[], int nd) {
  int n = strlen(s);
  int dp[n + 1];
  for (int i = 0; i <= n; i++) dp[i] = 0;
  dp[0] = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < i; j++)
      if (dp[j] && inDict(s + j, i - j, dict, nd)) {
        dp[i] = 1; break;
      }
  return dp[n];
}
function wordBreak(s, dict) {
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++)
    for (let j = 0; j < i; j++)
      if (dp[j] && dict.has(s.slice(j, i))) {
        dp[i] = true; break;
      }
  return dp[s.length];
}

In an interview

LeetCode 139, Word Break: can the text be split into a sequence of dictionary words?

Put the words in a hash set. Checking only j values within the longest word’s length cuts the work a lot.

More dynamic programming