Leetcode 1048. Longest String Chain

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

1. Description

Longest String Chain

2. Solution

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

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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] + 1
return max(chains.values())


def predecessor(self, a, b):
i = 0
j = 0
while i < len(a) and j < len(b):
if a[i] == b[j]:
i += 1
j += 1
else:
j += 1
if j - i > 1:
return False
return True

Version 2

1
2
3
4
5
6
7
8
9
10
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/
如果有收获,可以请我喝杯咖啡!