58. Word Break

MediumString Dynamic Programming Hash Table

Given a string s and a list of dictionary words wordDict, return true if s can be cut into a sequence of one or more pieces where every piece is a dictionary word.

A dictionary word may be used any number of times, and not every word has to be used.

Example 1

Input: s = "icecreamcone", wordDict = ["ice","cream","cone","icecream"]
Output: true

Explanation: "ice" + "cream" + "cone" works (so does "icecream" + "cone").

Example 2

Input: s = "catcat", wordDict = ["cat"]
Output: true

Explanation: The same word can be reused.

Example 3

Input: s = "dogsandcat", wordDict = ["dog","dogs","sand","and","cats"]
Output: false

Explanation: Both "dog" + "sand" and "dogs" + "and" leave "cat", which is not in the dictionary.

Constraints

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and every word consist of lowercase English letters
All words in wordDict are distinct

Follow-up: How would you return every possible segmentation instead of just whether one exists?

💡 Hint 1

Trying every possible first word and recursing is correct but can be exponential: the same suffix gets re-checked many times.

💡 Hint 2

Let ok[i] mean "the first i characters can be segmented". ok[0] is true.

💡 Hint 3

ok[i] is true if some j < i has ok[j] true and s.slice(j, i) in the dictionary. Put the words in a hash set, and only look back as far as the longest word.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

DP over prefixes. ok[i] is true when s[0..i) splits into dictionary words; ok[0] = true for the empty prefix. For each end position i, look at every start j no more than the longest word length back: if ok[j] holds and s[j..i) is in a hash set of the words, then ok[i] is true. The answer is ok[s.length]. Each prefix is solved once, which avoids the exponential blow-up of naive backtracking on inputs like "aaaa…ab".

Time O(n · L²) for n = s.length and L = longest word (substring hashing costs O(L))Space O(n + total dictionary size)

function wordBreak(s, wordDict) {
  const words = new Set(wordDict);
  let maxLen = 0;
  for (const w of wordDict) maxLen = Math.max(maxLen, w.length);
  const ok = new Array(s.length + 1).fill(false);
  ok[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = i - 1; j >= Math.max(0, i - maxLen); j--) {
      if (ok[j] && words.has(s.slice(j, i))) {
        ok[i] = true;
        break;
      }
    }
  }
  return ok[s.length];
}

class Solution {
    public boolean wordBreak(String s, String[] wordDict) {
        Set<String> words = new HashSet<>(Arrays.asList(wordDict));
        int maxLen = 0;
        for (String w : wordDict) maxLen = Math.max(maxLen, w.length());
        boolean[] ok = new boolean[s.length() + 1];
        ok[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = i - 1; j >= Math.max(0, i - maxLen); j--) {
                if (ok[j] && words.contains(s.substring(j, i))) {
                    ok[i] = true;
                    break;
                }
            }
        }
        return ok[s.length()];
    }
}

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
function wordBreak(s, wordDict) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit