Longest Stepwise Word
MediumTries & Strings
Problem
A word is stepwise in a list if it can be built one letter at a time, adding a letter to the end at each step, so that every intermediate word (starting from its first letter) is also in the list.
Given words, return the longest stepwise word. If several have the same length, return the lexicographically smallest. If none exists, return the empty string.
Example 1
- Input:
- words = ["c","ca","cat","cats","d","do","dog","dogs","cab"]
- Output:
- "cats"
"cats" and "dogs" are both stepwise with length 4; "cats" is smaller.
Example 2
- Input:
- words = ["apple","app","ap","a","apply","appl"]
- Output:
- "apple"
Example 3
- Input:
- words = ["bc","abc"]
- Output:
- ""
No one-letter word exists, so nothing can be built.
Constraints
- 1 ≤ words.length ≤ 1000
- 1 ≤ words[i].length ≤ 30
- Lowercase English letters.
Hint
Show the first hint
A stepwise word corresponds to a path in a trie where every node along the way is a word end.
Walkthrough
How to approach it
01Clarify before coding
- Must the chain start at a single letter? Yes, every prefix of the word must be in the list.
- Tie-break? Lexicographically smallest among the longest.
- No stepwise word? Return "".
02Brute force
Put words in a set; for each word check all its prefixes against the set; keep the best.
Cost: O(N·L²) with slicing (O(N·L) with hashing tricks). Acceptable, but the trie version shows the structure directly.
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.