Halo

A magic place for coding

0%

LeetCode 解题报告(378) -- 1048. Longest String Chain

Problem

Given a list of words, each word consists of English lowercase letters.

Let’s say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, "abc" is a predecessor of "abac".

A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.

Return the longest possible length of a word chain with words chosen from the given list of words.

Example 1:

1
2
3
Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chain is "a","ba","bda","bdca".

Example 2:

1
2
Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5

Constraints:

  • 1 <= words.length <= 1000
  • 1 <= words [i].length <= 16
  • words [i] only consists of English lowercase letters.

Analysis

   这道题是单词链问题,题目给出一堆单词,形成链的条件是:后一个单词比前一个单词长度多 1,而且仅有一个字符不同。题目要求的是最长单词链长度。

   首先求最长的长度,这种就可以往 dp 上面靠。定义 dp [i]words [i] 的单词链最长长度。如果 words [j]words [i] 的 predecessor,状态转移方程为 dp [i] = max (dp [i], dp [j] + 1)。所以重点就在于如何判断是 predecessor。

   首先是长度,前一个单词的长度假设为 x,则后一个单词必须是 x + 1。长度满足要求后,再检查不同的字符是否只有一个,如果都满足则说明是 predecessor。

   由于这里检查对长度有限制,所以我们先对所有的单词按照长度进行排序,然后从左到右开始遍历,先遍历长度较短的。


Solution

   无


Code

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
class Solution {
public:
int longestStrChain(vector<string>& words) {
sort (words.begin (), words.end (), [](string &A, string &B) {
return A.size () < B.size ();
});
int size = words.size ();

vector<int> dp(size, 1);

int result = 1;
for (int i = 0; i < size; i++) {
for (int j = 0; j < i; j++) {
if (words [i].size () == words [j].size ()) {
break;
}
if (words [i].size () - 1 > words [j].size ()) {
continue;
}
if (isPredecessor (words [j], words [i])) {
dp [i] = max (dp [i], dp [j] + 1);
result = max (result, dp [i]);
}
}
}
return result;
}
private:
bool isPredecessor(string A, string B) {
bool flag = false;
int idx1 = 0, idx2 = 0;
while (idx1 < A.size () && idx2 < B.size ()) {
if (A [idx1] == B [idx2]) {
idx1++;
idx2++;
} else if (!flag) {
flag = true;
idx2++;
} else {
return false;
}
}
return true;
}
};

Summary

   这道题是 dp 经典题之一,dp 的定义和状态转移都比较简单,难点是 dp 转移时的判断逻辑。这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels