Leetcode 1048. Longest String Chain

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

**解析：**Version 1，先根据字符串长度对数组排序，然后根据长度分到不同的组里，按长度遍历组，如果下一组的字符串长度比当前组多1个，则遍历两组的所有元素，满足条件前辈子串，则下一组子串的字符链长度在当前子串长度的基础上加1，其实就是一个广度优先搜索的过程。Version 2遍历字符串所有长度减1的子串，如果找到，则比较字符链长度，判断是否需要加1，返回最大长度。

• Version 1

class Solution:def longestStrChain(self, words: List[str]) -> int:stat ={
    }words.sort(key=len)for word in words:stat[len(word)] = stat.get(len(word), []) + [word]chains = {
    word: 1 for word in words}for k, v in stat.items():if k+1 in stat:for a in v:for b in stat[k+1]:if chains[b] <= chains[a] and self.predecessor(a, b):chains[b] = chains[a] + 1return max(chains.values())def predecessor(self, a, b):i = 0j = 0while i < len(a) and j < len(b):if a[i] == b[j]:i += 1j += 1else:j += 1if j - i > 1:return Falsereturn True

Version 2

class Solution:def longestStrChain(self, words: List[str]) -> int:words.sort(key=len)stat = {
    word: 1 for word in words}for word in words:for i in range(len(word)):pre = word[:i] + word[i+1:]if pre in stat:stat[word] = max(stat[word], stat[pre] + 1)return max(stat.values())

Reference

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