You are given an array of words
where each word consists of lowercase English letters.
\(word_A\) is a predecessor of \(word_B\) if and only if we can insert exactly one letter anywhere in \(word_A\) without changing the order of the other characters to make it equal to \(word_A\).
For example, "abc
" is a predecessor of "abac
", while "cba
" is not a predecessor of "bcad
".
A word chain is a sequence of words [word1, word2, ..., wordk]
with k >= 1
, where word1
is a predecessor of word2
, word2
is a predecessor of word3
, and so on. A single word is trivially a word chain with k == 1
.
Return the length of the longest possible word chain with words chosen from the given list of words.
Solution
我们用 \(map\) 来定义 \(dp\) 数组。现将原来的序列排序,得到长度从小到大的序列。
定义 \(dp[s]\) 表示以 \(s\) 结尾的最长 word chain 长度,考虑如何转移:
\[dp[s] = \max(dp[s], 1+dp[s']) \]其中 \(s'\) 为 \(s\) 的前驱。这里用 \(erase\) 函数,我们遍历当前的串 \(s\), 看删去一个位置后得到的 \(s'\) 是否在 \(map\) 中
点击查看代码
class Solution {
private:
map<string, int> dp;
int ans = INT_MIN;
public:
int longestStrChain(vector<string>& words) {
int n = words.size();
sort(words.begin(), words.end(),
[](string& s1, string& s2){return s1.size()<s2.size();});
for(int i=0;i<n;i++){
dp[words[i]]=1;
for(int j=0;j<words[i].size();j++){
string tmp = words[i];
tmp.erase(tmp.begin()+j);
if(dp[tmp])dp[words[i]] = max(1+dp[tmp], dp[words[i]]);
}
ans = max(ans, dp[words[i]]);
}
return ans;
}
};