Glossary Segmentation Check
Medium1-D Dynamic Programming
Problem
A search engine receives queries typed without spaces, like "sunsetstrip". Given the query s and a glossary words, decide whether s can be split into a sequence of one or more glossary words.
A glossary word may be used any number of times. Return true or false.
Example 1
- Input:
- s = "sunsetstrip", words = ["sun", "set", "sets", "trip", "strip", "unset"]
- Output:
- true
"sun" + "set" + "strip" (or "sun" + "sets" + "trip").
Example 2
- Input:
- s = "catsandog", words = ["cats", "dog", "sand", "and", "cat"]
- Output:
- false
Every split leaves "og" or "sandog" uncovered.
Constraints
- 1 ≤ s.length ≤ 300
- 1 ≤ words.length ≤ 1000
- 1 ≤ words[i].length ≤ 20
- s and words contain lowercase English letters only.
Hint
Show the first hint
Ask a smaller question: can the prefix s[0..i) be segmented?
Walkthrough
How to approach it
01Clarify before coding
- Can a word be reused? Yes, any number of times.
- Do I need to return the split? No, only whether one exists.
- Are there duplicates in the glossary? Possibly; a set removes them.
02Brute force
Recursively try every glossary word that matches the front of s, and recurse on the remaining suffix.
Cost: Exponential: for "aaaa...ab" with words a, aa, aaa the recursion revisits the same suffix through every combination of cuts before failing.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.