“This is the 25th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

First there is the concept of “predecessor” to understand:

Give an array of words in which each word is made up of a lowercase English letter.

If we can add exactly one letter anywhere in wordA to make it wordB without changing the order of the other characters, then we consider wordA to be the [predecessor] of wordB.

  • For example, “ABC” is the predecessor of “ABAC” and “CBA” is not the predecessor of “BCAD”

Second, to understand what a “word chain” is:

A word chain is a sequence of words [word_1, word_2,…, word_k], k >= 1, where word1 is the predecessor of word2, word2 is the predecessor of word3, and so on. A word is usually a chain of words with k == 1.

OK, or quite understandable ~~

Topic:

Returns the maximum possible length of the word chain by selecting words from the given word list words.

Such as:

Input: words = [" a ", "b", "ba", "bca", "bda," "bdca"] output: 4: one of the longest word chain for [" a ", "ba", "bda," "bdca"] input: Words = [" XBC PCXBCF ", ""," xb ", "CXBC", "PCXBC"] output: 5: all the words can be put into words chain [" xb ", "XBC", "CXBC", "PCXBC", "PCXBCF"].Copy the code

Answer:

Put the words in ascending order of length. Then walk through each word. Use a hash table to record the maximum length of each word as the last word in the chain.

Judge whether the word exists in the word list after removing one character. If it exists, word chain can be formed. Determine to update the word hash value.

Return the maximum hash value.

JavaScript implementation:

var longestStrChain = function(words) { words.sort((a, b) => a.length - b.length); const M = new Map(); let res = 1; for (let s of words) { if (M.has(s)) continue; // repeat m.et (s, 1); for (let i = 0; i < s.length; i++) { if (i > 0 && s[i] === s[i - 1]) continue; // repeat let t = s.substr(0, I) + s.substr(I + 1); if (M.has(t) && M.get(t) >= M.get(s)) { M.set(s, M.get(t) + 1); } } res = Math.max(res, M.get(s)); } return res; };Copy the code

OK, that’s it

I’m Nuggets Anthony, output exposure input, technical insight into life, goodbye ~~