题目描述
给出一个单词列表,其中每个单词都由小写英文字母组成。
如果我们可以在 word1
的任何地方添加一个字母使其变成 word2
,那么我们认为 word1
是 word2
的前身。例如,"abc"
是 "abac"
的前身。
词链是单词 [word_1, word_2, ..., word_k]
组成的序列,k >= 1
,其中 word_1
是 word_2
的前身,word_2
是 word_3
的前身,依此类推。
从给定单词列表 words
中选择单词组成词链,返回词链的最长可能长度。
样例
输入:["a","b","ba","bca","bda","bdca"]
输出:4
解释:最长单词链之一为 "a","ba","bda","bdca"。
注意
1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i]
仅由小写英文字母组成。
算法
(动态规划) $O(n^2m)$
- 首先将单词按长度从小到大排序。
- 和最长上升子序列类似,定义 $f(i)$ 表示以第
i
个单词结尾所能得到的最长的词链。 - 初始时,$f(i) = 1$,对于所有的
i
都成立。 - 如果 $j < i$ 且 $word[j]$ 是 $word[i]$ 的前身,则 $f(i) = \max (f(i), f(j) + 1)$。
- 判断前身的算法:两个串
a
和b
的长度只能相差 1,假设a
串的长度较小。定义两个指针分别指向a
和b
字符串,如果当前位置字符相等,则指针同时后移,否则,只移动b
的指针。最后如果a
的指针到达了末尾,则说明可以完成匹配。 - 最终答案为 $\max (f(i))$。
时间复杂度
- 排序的时间复杂度为 $O(n \log n)$。
- 动态规划状态数为 $O(n)$,转移枚举的个数为 $O(n)$,检查前身的时间复杂度为 $O(m)$,其中 $m$ 为字符串的长度。
- 总时间复杂度为 $O(n^2m)$。
空间复杂度
- 需要额外 $O(n)$ 的空间记录动态规划的状态。
C++ 代码
class Solution {
public:
static bool cmp(const string &a, const string &b) {
return a.length() < b.length();
}
bool check(const string &a, const string &b) {
if (a.length() + 1 != b.length())
return false;
int i = 0, j = 0;
while (i < a.length() && j < b.length()) {
if (a[i] == b[j]) {
i++;
j++;
} else {
j++;
}
}
return i == a.length();
}
int longestStrChain(vector<string>& words) {
sort(words.begin(), words.end(), cmp);
int n = words.size();
vector<int> f(n, 1);
for (int i = 1; i < n; i++)
for (int j = i - 1; j >= 0 && words[j].length() + 1 >= words[i].length(); j--)
if (check(words[j], words[i]))
f[i] = max(f[i], f[j] + 1);
int ans = 0;
for (int i = 0; i < n; i++)
ans = max(ans, f[i]);
return ans;
}
};