leetcode 1048. Longest String Chain
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 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.length <= 16
words 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 = 1;
int Max = 1;
for(int i = 1; i< words.size();i++){
int local = 0;
for(int j = 0 ; j < i ; j++){
if(words.size() - words.size() == 1 && isPredecessor(words, words)){
local = max(local, dp);
}
}
dp = local +1;
Max = max(Max, dp);
}
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 != b){
j++;
count++;
}
else{
i++;
j++;
}
}
if(count == 0 && i == a.size() && j != b.size()) return 1;
if(count == 1) return 1;
else return 0;
}
};
页:
[1]