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