- 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 chainis 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(17, vector<string>());
- for(auto Word:words)
- len_word[Word.size()].push_back(Word);
- map<string,int> dp;
- int res=0;
- for(int i=16;i>=1;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()-1])
- Set.insert(Word);
- int nowres=1;
- for(int i=0; i<nowword.size(); i++)
- {
- string temp=nowword;
- temp.erase(i,1);
- if(Set.count(temp))
- nowres = max(nowres,dfs(len_word,temp,dp)+1);
- }
- return dp[nowword]=nowres;
- }
- };
来源: http://www.bubuko.com/infodetail-3064388.html