Word break

Medium TimeO(n²·m) SpaceO(n)

Given a string s and a dictionary words, say whether s can be cut entirely into dictionary words. Every character must be used and every piece must be a word, words may be reused as often as needed, and an empty string is breakable, trivially.

Examples

Example 1

Input
s = "applepenapple"dictionary = ["apple", "pen"]
Output
true
apple, pen, apple — apple is used twice, which is allowed.

Example 2

Input
s = "catsandog"dictionary = ["cats", "dog", "sand", "and", "cat"]
Output
false
cat sand and cats and both leave og, which is not in the dictionary.

The Code

function wordBreak(s, dictionary) {
  const reachable = new Array(s.length + 1).fill(false);
  reachable[0] = true;
  for (let end = 1; end <= s.length; end++) {
    for (let start = 0; start < end; start++) {
      if (!reachable[start]) continue;
      const piece = s.slice(start, end);
      if (dictionary.indexOf(piece) !== -1) {
        reachable[end] = true;
        break;
      }
    }
  }
  return reachable[s.length];
}
wordBreak("applepenapple", ["apple", "pen"]);
Done

The first 18 calls, of 109. This one does not fit on a page.

Step through wordBreak("applepenapple", ["apple", "pen"]) call by call

More like this

All dynamic programming examples (20) →