Word Break

MediumString Dynamic Programming Hash Table

Screen readers stumble over hashtags such as #sunsetbeachday because the words run together. A social app wants to know whether a lowercase hashtag s can be split into words from its dictionary, wordDict.

Return true if s can be cut into one or more pieces where every piece is a dictionary word, and false otherwise. A dictionary word may be used any number of times, and not every word has to be used.

Example 1

Input: s = "sunsetbeachday", wordDict = ["sun","set","sunset","beach","day"]
Output: true

Explanation: sunset + beach + day works, and so does sun + set + beach + day.

Example 2

Input: s = "gogogo", wordDict = ["go"]
Output: true

Explanation: The same word can be used again and again.

Example 3

Input: s = "seashells", wordDict = ["sea","seas","shell","hell"]
Output: false

Explanation: Both sea + shell and seas + hell leave a stray s at the end.

Constraints

s is between 1 and 300 characters long.
wordDict holds between 1 and 1000 distinct words, each 1 to 20 characters long.
s and every dictionary word use only lowercase English letters.

Follow-up: How would you list every possible way to split the hashtag, instead of only reporting 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