给出一个单词列表,其中每个单词都由小写英文字母组成。
如果我们可以在 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] 仅由小写英文字母组成。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-string-chain 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
dp[i]
表示以单词 i
结束的链的最大长度
见代码注释class Solution {
public:
int longestStrChain(vector<string>& words) {
sort(words.begin(),words.end(),[&](auto a, auto b){
return a.size() < b.size();//按长度排序
});
int n = words.size(), maxlen = 1, i, j, k;
unordered_map<string, int> s;//哈希
string tmp;
vector<int> dp(n, 1);
for(i = 0; i < n-1; ++i)
{
s[words[i]] = i;//建立哈希
j = i+1;
for(k = 0; k < words[j].size(); ++k)
{ //遍历后面长的单词,枚举所有少一个字符的子串
tmp = words[j].substr(0,k)+words[j].substr(k+1);
if(s.find(tmp) != s.end())//存在这个子串
{
dp[j] = max(dp[j], dp[s[tmp]]+1);
maxlen = max(maxlen, dp[j]);
}
}
}
return maxlen;
}
};
268 ms 25.2 MB