# 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