1048. Longest String Chain
https://leetcode.com/problems/longest-string-chain/
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.
解法：动态规划
对于任意word，任意删去其中一个字母后为word'，若word'在words中，则dp[word] = max(dp[word], dp[word'] + 1)。
先将所有words按长度存储。在计算dp[word]时，先将words中长度为word.size()-1的单词放入一个set，方便word'是否在words中。
class Solution
{
public:
int longestStrChain(vector<string>& words)
{
vector<vector<string>> len_word(, vector<string>());
for(auto word:words)
len_word[word.size()].push_back(word);
map<string,int> dp;
int res=;
for(int i=;i>=;i--)
{
if(i<res)
break;
for(auto word:len_word[i])
res = max(res,dfs(len_word,word,dp));
}
return res;
}
int dfs(vector<vector<string>>& len_word,string& nowword, map<string,int>& dp)
{
//cout<<nowword<<endl;
if(dp.count(nowword))
return dp[nowword];
set<string> Set;
for(auto word:len_word[nowword.size()-])
Set.insert(word);
int nowres=;
for(int i=; i<nowword.size(); i++)
{
string temp=nowword;
temp.erase(i,);
if(Set.count(temp))
nowres = max(nowres,dfs(len_word,temp,dp)+);
}
return dp[nowword]=nowres;
}
};