1048. Longest String Chain

题目信息

题号:

1048

难度:

Medium

主题:

字符串序列、前驱关系、最长链

原题:

LeetCode 1048

重点:

后继单词必须由前驱单词恰好插入一个字母得到,原有字母相对顺序不能改变;链中单词来自输入数组

题目重述

给定互不相同的小写单词数组 words。若能在单词 wordA 的任意位置插入恰好一个小写字母,并保持原有字符相对顺序不变,从而得到 wordB,则 wordA 是 wordB 的前驱。

字符串链是一列来自 words 的单词,相邻两项满足前驱关系。请返回能够形成的最长字符串链长度;输入单词在数组中的原始顺序不限制链的排列。

1 <= words.length <= 1000,1 <= words[i].length <= 16,每个单词只包含小写英文字母且互不相同。

自建示例

每一步可以在不同位置插入字母:

输入:words = ["i","in","pin","spin","spine","pine"]
输出:5
解释:可以形成 i -> in -> pin -> spin -> spine,每一步都恰好插入一个字母,因此链长为 5。

输入只有一个单词:

输入:words = ["code"]
输出:1
解释:单个单词自身构成长度为 1 的字符串链。