1048-最长字符串链

Raphael Liu Lv10

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

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

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

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

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

示例 1:

**输入:** words = ["a","b","ba","bca","bda","bdca"]
**输出:** 4
**解释:** 最长单词链之一为 ["a"," _b_ a","b _d_ a","bd _c_ a"]

示例 2:

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

示例 3:

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

提示:

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

方法一:动态规划

思路与算法

根据题意可知,对于字符串「前身」的定义为:

  • 不改变其他字符的顺序 ,在 wordA 的任何地方添加恰好一个字母使其变成 wordB,那么我们认为 wordA 是 wordB 的前身。
  • 将 wordB 中去掉任意一个字母,其余字符保持不变构成的字符串即为 wordB 的前身。

因此对于每个字符串 s,假设其所有的前身 s’ 为结尾的最长链的长度为 l,即可知道以 s 为结尾的最长链的长度为 l + 1。为保证我们求 s 的最长链时,其所有的前身的最长链的长度均已求出,需要将所有的字符串按照长度大小进行排序。假设字符串 s 最长链的长度为 cnt}(s) 的前身为 s’{0},s’{1},s’{2}, \cdots,s’{k,则此时可以知道

\textit{cnt}(s) = \max(\textit{cnt}(s’_{i})), \quad i \in [0,k]

根据以上结论,实际计算过程如下:

  • 首先对字符串数组 words 按照字符串长度的大小进行排序;
  • 依次遍历每个字符串 words}[i],并初始以 words}[i] 为结尾的最长链的长度 cnt}[\textit{words}[i]] 为 1;
  • 依次尝试去掉 words}[i] 中的每个字符,并构成其可能的前身 prev,在哈希表 cnt 查找 prev 对应的最长链长度,如果 cnt} + 1 大于 cnt}[\textit{words}[i]],则更新 cnt}[\textit{words}[i]];
  • 最终返回可能的最长链的长度即可。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int longestStrChain(vector<string>& words) {
unordered_map<string, int> cnt;
sort(words.begin(), words.end(), [](const string &a, const string &b) {
return a.size() < b.size();
});
int res = 0;
for (string word : words) {
cnt[word] = 1;
for (int i = 0; i < word.size(); i++) {
string prev = word.substr(0, i) + word.substr(i + 1);
if (cnt.count(prev)) {
cnt[word] = max(cnt[word], cnt[prev] + 1);
}
}
res = max(res, cnt[word]);
}
return res;
}
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int longestStrChain(String[] words) {
Map<String, Integer> cnt = new HashMap<String, Integer>();
Arrays.sort(words, (a, b) -> a.length() - b.length());
int res = 0;
for (String word : words) {
cnt.put(word, 1);
for (int i = 0; i < word.length(); i++) {
String prev = word.substring(0, i) + word.substring(i + 1);
if (cnt.containsKey(prev)) {
cnt.put(word, Math.max(cnt.get(word), cnt.get(prev) + 1));
}
}
res = Math.max(res, cnt.get(word));
}
return res;
}
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def longestStrChain(self, words: List[str]) -> int:
cnt = defaultdict(int)
words.sort(key=len)
res = 0
for word in words:
cnt[word] = 1
for i in range(len(word)):
prev = word[:i] + word[i+1:]
if prev in cnt:
cnt[word] = max(cnt[word], cnt[prev] + 1)
res = max(res, cnt[word])
return res
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public int LongestStrChain(string[] words) {
IDictionary<string, int> cnt = new Dictionary<string, int>();
Array.Sort(words, (a, b) => a.Length - b.Length);
int res = 0;
foreach (string word in words) {
if (cnt.ContainsKey(word)) {
cnt[word] = 1;
} else {
cnt.Add(word, 1);
}
for (int i = 0; i < word.Length; i++) {
string prev = word.Substring(0, i) + word.Substring(i + 1);
if (cnt.ContainsKey(prev)) {
cnt[word] = Math.Max(cnt[word], cnt[prev] + 1);
}
}
res = Math.Max(res, cnt[word]);
}
return res;
}
}
[sol1-C]
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
typedef struct {
char *key;
int val;
UT_hash_handle hh;
} HashItem;

HashItem *hashFindItem(HashItem **obj, char *key) {
HashItem *pEntry = NULL;
HASH_FIND_STR(*obj, key, pEntry);
return pEntry;
}

bool hashAddItem(HashItem **obj, char *key, int val) {
if (hashFindItem(obj, key)) {
return false;
}
HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
pEntry->key = key;
pEntry->val = val;
HASH_ADD_STR(*obj, key, pEntry);
return true;
}

bool hashSetItem(HashItem **obj, char *key, int val) {
HashItem *pEntry = hashFindItem(obj, key);
if (!pEntry) {
hashAddItem(obj, key, val);
} else {
pEntry->val = val;
}
return true;
}

int hashGetItem(HashItem **obj, char *key, int defaultVal) {
HashItem *pEntry = hashFindItem(obj, key);
if (!pEntry) {
return defaultVal;
}
return pEntry->val;
}

void hashFree(HashItem **obj) {
HashItem *curr = NULL, *tmp = NULL;
HASH_ITER(hh, *obj, curr, tmp) {
HASH_DEL(*obj, curr);
free(curr);
}
}

static int cmp(const void *pa, const void *pb) {
return strlen(*(char **)pa) - strlen(*(char **)pb);
}

int longestStrChain(char ** words, int wordsSize) {
HashItem *cnt = NULL;
qsort(words, wordsSize, sizeof(char *), cmp);
int res = 0;
for (int i = 0; i < wordsSize; i++) {
hashAddItem(&cnt, words[i], 1);
char prev[32];
for (int j = 0; words[i][j] != '\0'; j++) {
strcpy(prev + j, words[i] + j + 1);
if (hashFindItem(&cnt, prev)) {
int len = hashGetItem(&cnt, prev, 0) + 1;
int cur = hashGetItem(&cnt, words[i], 0);
if (len > cur) {
hashSetItem(&cnt, words[i], len);
}
}
prev[j] = words[i][j];
}
int cur = hashGetItem(&cnt, words[i], 0);
if (cur > res) {
res = cur;
}
}
hashFree(&cnt);
return res;
}
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func longestStrChain(words []string) int {
cnt := map[string]int{}
sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
res := 0
for _, word := range words {
cnt[word] = 1
for i := range word {
prev := word[:i] + word[i + 1:]
if j := cnt[prev] + 1; j > cnt[word] {
cnt[word] = j
}
}
if cnt[word] > res {
res = cnt[word]
}
}
return res
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var longestStrChain = function(words) {
const cnt = new Map();
words.sort((a, b) => a.length - b.length);
let res = 0;
for (const word of words) {
cnt.set(word, 1);
for (let i = 0; i < word.length; i++) {
const prev = word.substring(0, i) + word.substring(i + 1);
if (cnt.has(prev)) {
cnt.set(word, Math.max(cnt.get(word), cnt.get(prev) + 1));
}
}
res = Math.max(res, cnt.get(word));
}
return res;
};

复杂度分析

  • 时间复杂度:O(n \times m \times (\log n + m)),其中 n 表示字符串数组的长度,m 表示每个字符串的平均长度。首选对字符串数组进行排序,需要的时间为 O(n \times m \times \log n),然后遍历每个字符串,并对每个字符串都生成其「前身」字符串,需要的时间为 O(n \times m^2),因此总的时间复杂度为 O(n \times m \times (\log n + m))。

  • 空间复杂度:O(n\times m),其中 n 表示字符串数组的长度,m 表示每个字符串的平均长度。需要存储以每个字符串为结尾的最大链的长度,一共有 n 个字符串,每个字符串的平均长度为 m,因此需要的空间为 O(n\times m)。

 Comments
On this page
1048-最长字符串链