#637 · Dynamic programming · Advanced · Fast enough · 150 XP · about 30 min
In a word chain each word is made from the one before it by inserting exactly one letter, at the front, at the end or anywhere in between, without moving the other letters. For example, a, at, cat, cart and chart form a chain of 5 words.
Write longest_chain(words) that returns the number of words in the longest chain that uses only words from words. A single word is a chain of 1, and an empty list gives 0.
longest_chain(['a', 'at', 'cat', 'cart', 'chart', 'dog']) # returns 5 longest_chain(['b', 'ab', 'abc', 'xyz', 'abcd']) # returns 4 longest_chain(['tea', 'eat', 'ate']) # returns 1
The last example has no chain longer than one word: the three words have the same letters, but none is made from another by inserting a letter.
0 <= len(words) <= 60,000Each test must finish within 10 seconds, and the hidden tests use lists of tens of thousands of words.
First solves only, ranked by stars and then time.