最长字符串链

标签: 数组 哈希表 双指针 字符串 动态规划

难度: Medium

给出一个单词数组 words ，其中每个单词都由小写英文字母组成。

如果我们可以 不改变其他字符的顺序 ，在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的 前身 。

  • 例如，"abc" 是 "abac" 的 前身 ，而 "cba" 不是 "bcad" 的 前身

词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的 单词链 。

从给定单词列表 words 中选择单词组成词链，返回 词链的 最长可能长度 。
 

示例 1：

输入：words = ["a","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 ["a","ba","bda","bdca"]

示例 2:

输入：words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
输出：5
解释：所有的单词都可以放入单词链 ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

示例 3:

输入：words = ["abcd","dbqca"]
输出：1
解释：字链["abcd"]是最长的字链之一。
["abcd"，"dbqca"]不是一个有效的单词链，因为字母的顺序被改变了。

提示：

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 16
  • words[i] 仅由小写英文字母组成。

Submission

运行时间: 68 ms

内存: 16.3 MB

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        d = {}

        mp = defaultdict(lambda: 1)
        maxd = 0
        for w in words:
            if len(w) in d:
                d[len(w)].append(w)
            else:
                d[len(w)] = [w]
            maxd = max(maxd, len(w))
        
        fad = maxd 
        ans = 1
        while fad > 1:
            if  (fad-1) in d and len(d[fad-1]) > 0:
                child = set(d[fad-1])
            else:
                fad -= 1
                continue
            if fad not in d:
                fad -= 1
                continue
            for wf in d[fad]:
                for i in range(fad):
                    tmp = wf[:i] + wf[i+1:]
                    if tmp in child:
                        mp[tmp] = max(mp[tmp], mp[wf] + 1)
                        ans = max(mp[tmp], ans)
            fad -= 1

        return ans

Explain

此题解采用动态规划的思想，核心是用哈希表d记录每个单词长度对应的单词列表，同时使用哈希表mp存储到当前单词为止可能形成的最长字符串链的长度。首先，将单词按长度分类并存入d中，并记录最长单词的长度maxd。接着，从最长单词长度开始，向下查找可能的前身单词。如果长度为fad的单词能通过删除一个字符得到长度为fad-1的单词，则更新该前身单词在mp中的值。整个过程从最大长度递减到1，每次尝试通过删除操作找到可能的前身，并更新最长链的长度。

时间复杂度: O(N*fad^2)

空间复杂度: O(N)

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        # 字典d存储每个长度的单词列表
        d = {}
        # 默认字典mp记录最长字符串链的长度，默认值为1
        mp = defaultdict(lambda: 1)
        # 记录最长单词的长度
        maxd = 0
        for w in words:
            if len(w) in d:
                d[len(w)].append(w)
            else:
                d[len(w)] = [w]
            maxd = max(maxd, len(w))
        # 从最大长度开始处理
        fad = maxd 
        ans = 1
        while fad > 1:
            if  (fad-1) in d and len(d[fad-1]) > 0:
                child = set(d[fad-1])
            else:
                fad -= 1
                continue
            if fad not in d:
                fad -= 1
                continue
            for wf in d[fad]:
                for i in range(fad):
                    # 删除一个字符，形成新单词tmp
                    tmp = wf[:i] + wf[i+1:]
                    # 检查tmp是否为有效前身
                    if tmp in child:
                        mp[tmp] = max(mp[tmp], mp[wf] + 1)
                        ans = max(mp[tmp], ans)
            fad -= 1
        return ans

Explore

为了确保在删除字符的过程中不漏掉任何可能的前身单词，算法对每个单词尝试删除其每个位置上的字符。具体来说，对长度为 fad 的单词 wf，算法会依次删除从第一个字符到最后一个字符，生成 fad-1 长度的所有可能单词，并检查这些单词是否存在于单词列表中。这种方法通过遍历单词的每个字符位置并尝试删除，确保了考虑了所有可能的删除方式。

在题解中，哈希表 d 用于存储按长度分类的单词列表。这样可以快速访问特定长度的所有单词，从而在检查可能的前身单词时提高效率。哈希表 mp 用来存储每个单词对应的最长字符串链的长度。它记录了从当前单词开始，可以向前追溯形成的最长字符串链的长度，这样在检查新的单词时可以快速更新其可能的最长前身链长度。

尝试删除每个位置的字符确实可能导致效率问题，特别是当单词长度非常长时。对于一个长度为 n 的单词，这种方法需要进行 n 次操作来生成所有可能的前身单词，并且每次操作都需要检查新生成的单词是否存在于单词列表中，这可能导致较高的时间复杂度。尽管如此，由于单词长度通常有限，这种方法在实际应用中可能仍然是可行的，但对于极端情况确实需要考虑更高效的算法。

题解通过使用集合 child 来确保通过删除字符得到的新单词确实存在于单词列表中。在处理特定长度的单词时，会创建一个集合 child，其中包含所有长度为 fad-1 的单词。然后，对于每个长度为 fad 的单词，通过删除字符生成新单词后，会检查这个新单词是否存在于 child 集合中。这种方法利用集合的快速查找功能，有效确保了只有存在于单词列表中的前身才会被计入最长字符串链的计算。