# Halo

A magic place for coding

0%

## Problem

Given a list of words, each word consists of English lowercase letters.

Let’s say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, "abc" is a predecessor of "abac".

A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.

Return the longest possible length of a word chain with words chosen from the given list of words.

Example 1:

Example 2:

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 16
• words[i] only consists of English lowercase letters.

## Analysis

这道题是单词链问题，题目给出一堆单词，形成链的条件是：后一个单词比前一个单词长度多1，而且仅有一个字符不同。题目要求的是最长单词链长度。

首先求最长的长度，这种就可以往dp上面靠。定义dp[i]words[i]的单词链最长长度。如果words[j]words[i]的predecessor，状态转移方程为dp[i] = max(dp[i], dp[j] + 1)。所以重点就在于如何判断是predecessor。

首先是长度，前一个单词的长度假设为x，则后一个单词必须是x + 1。长度满足要求后，再检查不同的字符是否只有一个，如果都满足则说明是predecessor。

由于这里检查对长度有限制，所以我们先对所有的单词按照长度进行排序，然后从左到右开始遍历，先遍历长度较短的。

无

## Summary

这道题是dp经典题之一，dp的定义和状态转移都比较简单，难点是dp转移时的判断逻辑。这道题目的分享到这里，感谢你的支持！

Welcome to my other publishing channels