Split text into the fewest dictionary words with tie-breaking
Hashtags, domain names, and URL slugs often glue words together: sunflowerseed, bluemoonbakery. Implement segmentWords(text, dictionary), which splits text into dictionary words and returns the split that uses the fewest words.
segmentWords(text, dictionary) // => string[] | null
dictionary that, joined with no separator, equal text exactly.'Sun' does not match 'sun'.dictionary are ignored. Duplicate entries are allowed.text is '', return []. If no split exists, return null.segmentWords('sunflowerseed', ['sun', 'flower', 'sunflower', 'seed', 'flowers', 'eed']);
// => ['sunflower', 'seed']
// (sun + flower + seed and sun + flowers + eed use three words)
segmentWords('icecreamcone', ['ice', 'cream', 'icecream', 'cone', 'creamcone']);
// => ['icecream', 'cone']
// (ice + creamcone also uses two words, but 'icecream' is the longer first word)
segmentWords('nonono', ['no', 'non', 'o']);
// => ['non', 'o', 'no']
// (no + no + no also uses three words, but 'non' is longer than 'no')
segmentWords('bluemoon', ['blue', 'Moon']);
// => null
segmentWords('', ['a']);
// => []
Texts can be up to 1,000 characters and dictionaries up to 1,000 words. Inputs such as 'aaaa…ab' with ['a', 'aa', 'aaa'] have an exponential number of partial splits, so a plain backtracking search will time out.