FunctionRacerProblemsRace

Longest Insertion Ladder

MediumDynamic programmingPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems