Extra Characters in a String

Extra Characters in a String: the approach in brief

The problem

Given a string s and a collection of distinct words in dictionary, split s into consecutive, non-overlapping pieces. A piece that exactly matches a word in dictionary contributes no extra characters; every other character contributes one extra character. Dictionary words may be used wherever they match, including more than once.

Pattern

Extra Characters in a String is a Design Patterns problem, in the Tries subpattern. The pattern covers tries, LRU/LFU cache, and data structure design

Approach outline

1. Consider solving the string from left to right and recording the best result for every prefix.
2. At a position, one option is to treat the current character as extra; another is to consume any dictionary word that starts there.
3. A trie can find all dictionary words matching a substring that begins at the current position without repeatedly comparing every complete word.

Complexity

The reference solution runs in O(n * d * L), where n is the length of s, d is the number of dictionary words, and L is the maximum dictionary-word length. time and O(n) auxiliary space. space.