Longest Insertion Ladder
A ladder is a sequence of words from words in which every word is the word before it with exactly one letter inserted somewhere: at the front, at the end, or between two letters. The other letters keep their order.
Return the length of the longest ladder. A single word is a ladder of length 1, and an empty list gives 0. The words in the list are all different and may come in any order.
Example 1
words ["t","at","cat","cart","chart","art","dog"]
returns 5
t, at, cat, cart, chart: each word adds one letter to the one before it.
Example 2
words ["abc","xyz","ab","bc"]
returns 2
ab grows into abc by adding c at the end. Nothing in the list grows from abc or xyz.
Constraints
0 <= len(words) <= 601 <= len(words[i]) <= 10- lowercase letters only; no word appears twice
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Longest Mirror SubsequenceMedium
- Loot Around the Lantern RingMedium
- Lowest Photo WallMedium
- Lucky Toll TripsMedium
- No Double LeapsMedium
- One Forgiven DayMedium
- Paint the FenceMedium
- Shared Subsequence LengthMedium