最长字符串链

Longest String Chain

问题：最长字符串链

考察：数组、哈希表、双指针

来源：DSA Prep / Citadel

链接：https://leetcode.com/problems/longest-string-chain

Problem: Longest String Chain

Patterns: Array, Hash Table, Two Pointers

Recency: 2yr

Link: https://leetcode.com/problems/longest-string-chain

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：按单词长度排序，dp[word] 表示以该单词结尾的最长链。对每个单词删除一个字符得到前驱，若前驱存在就用 dp[prev]+1 更新。

复杂度：设总字符数为 S，时间约 O(S * L)（切片实现相关），空间 O(n)。