自己写的,超时
class Solution {
public:
int longestStrChain(vector<string>& words) {
int maxn = 1;
for(int i = 0; i < words.size(); i++){
maxn = max(maxn, dfs(words[i],words));
}
return maxn;
}
int dfs(string a, vector<string>& words){
int maxn = 1;
for(int i = 0; i < words.size(); i++){
if(isPre(a, words[i])){
maxn = max(maxn, 1+dfs(words[i],words));
}
}
return maxn;
}
bool isPre(string a, string b){
if(a.length()+1 != b.length()){
return false;
}
for(int i = 0; i < a.length(); i++){
if(a[i] != b[i]){
for(int j = 0; j < 26; j++){
char c = 'a' + j;
a = a.substr(0,i) + c + a.substr(i);
if(a == b)
return true;
else
a = a.substr(0,i) + a.substr(i+1);
}
return false;
}
}
return true;
}
};
剪枝以后依旧超时,但是快了一些
class Solution {
public:
int longestStrChain(vector<string>& words) {
unordered_map<int,int> map;
int maxn = 1;
for(int i = 0; i < words.size(); i++){
if(!map[i]){
map[i] = dfs(i,words,map);
}
maxn = max(maxn, map[i]);
}
return maxn;
}
int dfs(int index, vector<string>& words,unordered_map<int,int> &map){
int maxn = 1;
for(int i = 0; i < words.size(); i++){
if(isPre(words[index], words[i])){
if(!map[i]){
map[i] = dfs(i,words,map);
}
maxn = max(maxn, 1+map[i]);
}
}
return maxn;
}
bool isPre(string a, string b){
if(a.length()+1 != b.length()){
return false;
}
for(int i = 0; i < a.length(); i++){
if(a[i] != b[i]){
for(int j = 0; j < 26; j++){
char c = 'a' + j;
a = a.substr(0,i) + c + a.substr(i);
if(a == b)
return true;
else
a = a.substr(0,i) + a.substr(i+1);
}
return false;
}
}
return true;
}
};
答案自底向上
class Solution {
public :
int longestStrChain(vector<string> &words) {
unordered_map<string, int> dp;
// Sorting the list in terms of the word length.
std::sort(words.begin(), words.end(), [](const std::string &word1, const std::string &word2) {
return word1.size() < word2.size();
});
int longestWordSequenceLength = 1;
for (const string &word : words) {
int presentLength = 1;
// Find all possible predecessors for the current word by removing one letter at a time.
for (int i = 0; i < word.length(); i++) {
string predecessor = word.substr(0, i) + word.substr(i + 1, word.length() + 1);
if (dp.find(predecessor) != dp.end()) {
int previousLength = dp[predecessor];
presentLength = max(presentLength, previousLength + 1);
}
}
dp[word] = presentLength;
longestWordSequenceLength = max(longestWordSequenceLength, presentLength);
}
return longestWordSequenceLength;
}
};
答案自顶向下
class Solution {
private:
int dfs(unordered_set<string> &words, unordered_map<string, int> &memo, string currentWord) {
// If the word is encountered previously we just return its value present in the map (memoization).
if (memo.find(currentWord) != memo.end()) {
return memo[currentWord];
}
// This stores the maximum length of word sequence possible with the 'currentWord' as the
int maxLength = 1;
// creating all possible strings taking out one character at a time from the `currentWord`
for (int i = 0; i < currentWord.length(); i++) {
string newWord = currentWord.substr(0, i) + currentWord.substr(i + 1);
// If the new word formed is present in the list, we do a dfs search with this newWord.
if (words.find(newWord) != words.end()) {
int currentLength = 1 + dfs(words, memo, newWord);
maxLength = max(maxLength, currentLength);
}
}
memo[currentWord] = maxLength;
return maxLength;
}
public :
int longestStrChain(vector<string> &words) {
unordered_map<string, int> memo;
unordered_set<string> wordsPresent;
for (const string &word : words) {
wordsPresent.insert(word);
}
int ans = 0;
for (const string &word : words) {
ans = max(ans, dfs(wordsPresent, memo, word));
}
return ans;
}
};
答案是改成哈希表了,这样查找快。
修改后自己的代码
class Solution {
public:
int longestStrChain(vector<string>& words) {
unordered_map<string,int> map;
unordered_set<string> wordsPresent;
for (const string &word : words) {
wordsPresent.insert(word);
}
int maxn = 0;
for(int i = 0; i < words.size(); i++){
if(!map[words[i]]){
map[words[i]] = dfs(words[i],wordsPresent,map);
}
maxn = max(maxn, map[words[i]]);
}
return maxn;
}
int dfs(string s, unordered_set<string>& words,unordered_map<string,int> &map){
int maxn = 1;
for(int i = 0; i < s.length(); i++){
string temp = s.substr(0,i)+s.substr(i+1);
if(words.find(temp) != words.end()){
if(!map[temp]){
map[temp] = dfs(temp, words, map);
}
maxn = max(maxn, 1+map[temp]);
}
}
return maxn;
}
};