1048. Longest String Chain¶
题目信息¶
- 题号:
1048
- 难度:
Medium
- 主题:
字符串序列、前驱关系、最长链
- 原题:
- 重点:
后继单词必须由前驱单词恰好插入一个字母得到,原有字母相对顺序不能改变;链中单词来自输入数组
题目重述¶
给定互不相同的小写单词数组 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 的字符串链。