|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- Given a list of words, each word consists of English lowercase letters.
- 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.
-
- Example 1:
- Input: ["a","b","ba","bca","bda","bdca"]
- Output: 4
- Explanation: one of the longest word chain is "a","ba","bda","bdca".
-
- Note:
- 1 <= words.length <= 1000
- 1 <= words[i].length <= 16
- words[i] only consists of English lowercase letters.
复制代码
- class Solution {
- public:
- int longestStrChain(vector<string>& words) {
- if(words.size() == 0) return 0;
- sort(words.begin(),words.end(),cmp);
- vector <int> dp(words.size(),0);
- dp[0] = 1;
- int Max = 1;
- for(int i = 1; i< words.size();i++){
- int local = 0;
- for(int j = 0 ; j < i ; j++){
- if(words[i].size() - words[j].size() == 1 && isPredecessor(words[j], words[i])){
- local = max(local, dp[j]);
- }
-
- }
- dp[i] = local +1;
-
- Max = max(Max, dp[i]);
- }
-
-
- return Max;
- }
- private:
- static bool cmp (const string &a, const string &b){
- return a.size() < b.size();
- }
-
- int isPredecessor(string a, string b){
- sort(a.begin(),a.end());
- sort(b.begin(),b.end());
- int count = 0;
- int i = 0, j = 0;
- while(i != a.size() && j != b.size()){
- if(a[i] != b[j]){
- j++;
- count++;
- }
- else{
- i++;
- j++;
- }
- }
- if(count == 0 && i == a.size() && j != b.size()) return 1;
- if(count == 1) return 1;
- else return 0;
-
- }
-
-
- };
复制代码 |
|