Problem Breakdown
Word Container
Published ·
medium
Try This Problem Yourself
Practice in the AI-enabled editor with real-time feedback
You're given a list of words. Return every word that contains at least one other word from the list as a proper substring. "Proper" means strictly shorter, so "app" does not contain "app". The output preserves the order words appear in the input.
["apple", "app", "banana", "nana"] → ["apple", "banana"]
["work", "worker", "rework"] → ["worker", "rework"]
["cat", "dog", "bird"] → []The surface area is tiny. The only knob is how you go about the substring check, and that's where the whole problem lives.
Pattern: String Matching & Parsing
The whole problem is deciding when one word sits inside another, which is substring matching. Picking the right structure to test containment quickly is what the string matching and parsing pattern is about.
Solution 1, checking every pair
The most natural way to think about this is one word at a time. Take each word and ask whether any other word in the list fits inside it as a substring. If at least one does, then that word is a container and you can move on to the next candidate.
Complexity
Where it breaks
Solution 2, enumerating substrings instead of pairs
Complexity
Where it breaks
Solution 3, walking a structure instead of materializing substrings
Why the trie wins on long words
What about Aho-Corasick?
Benchmarks
Takeaways
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium