String Chains

Interview

Description:

Given an array, words, of n word strings (words[0], words[1],..., words[n-1]), choose a word from it and, in each step, remove a single letter from the chosen word if and only if doing so yields another word that is already in the library. Each successive character removal should be performed on the result of the previous removal, and you cannot remove a character if the resulting string is not an element in words(see Explanation below for detail). The length of a string chain is the maximum number of strings in a chain of successive character removals.

Complete the longestChain function in your editor. It has 1 parameter: an array of n strings, words, where the value of each element words; (where 0 <= i < n) is a word. It must return single integer denoting the length of the longest possible string chain in words.

Example:

Sample Case 1: words = {"a", "b", "ba", "bca", "bda", "bdca"} 
Because "a" and "b" are single-character words, we cannot remove any characters from them as that would result in the empty string (which is not an element in words), 
so the length for both of these string chains is 1.

The word "ba" can create two different string chains of length 2 ("ba" -> "a" and "ba" -> "b"). 
This means our current longest string chain is 2.

The word "bca" can create two different string chains of length 3 ("bca" -> "ba" -> "a" and "bca" -> "ba" -> "b"). 
This means our current longest string chain is now 3.

The word "bda" can create two different string chains of length 3 ("bda" -> "ba" -> "a" and "bda" -> "ba" -> "b"). 
This means our current longest string chain is now 3.

The word "bdca" can create four different string chains of length 4 
("bdca" -> "bda" -> "ba" -> "a" , "bdca" -> "bda" -> "ba" -> "b", "bdca" -> "bca" -> "ba" -> "a", "bdca" -> "bca" -> "ba" -> "b"). 
This means our current longest string chain is now 4.

Idea:

类似longest Increasing Path in a Matrix之类，用DFS+DP（应该就算是DP），这题要用hash table来存已经计算过的值。

Code:

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;


int DFS(const vector<string>& , string, unordered_map<string, int> & , const unordered_set<string>&);

int longestChain(vector<string> &words){
    unordered_map<string, int> DP; // hash table to record the length of chain at each word
    unordered_set<string> words_set(words.begin(), words.end()); // use hash set for fast check

    for(const auto& e: words){
        DP[e]=0; // Initialize memo table.
    }

    int max_len=0;

    for(int i=0; i<words.size(); ++i){
        if(DP[words[i]]==0){
            max_len=max(max_len, DFS(words, words[i], DP, words_set));
        }
    }

    // // Debug purpose
    // for(auto e: DP){
    //     cout<<e.first<<' '<<e.second<<'\n';
    // }

    return max_len;
}

int DFS(const vector<string>& input, string word, unordered_map<string, int> & DP, const unordered_set<string>& words_set){
    if(DP[word]!=0) return DP[word];

    if(word.size()==1){
        DP[word]=1;  // Single letter word, length == 1
        return 1;
    }

    int longest=0;

    for(int i=0; i<word.size(); ++i){
        string sub_word=word.substr(0,i) + word.substr(i+1);
        if(words_set.find(sub_word)!=words_set.end()){
            longest = max(longest, DFS(input, sub_word, DP, words_set));
        }
    }

    DP[word] = longest+1;
    return DP[word];
}

int main(){
    // int N=6;
    vector<string> input={"a", "b", "ba", "bca", "bda", "bdca"};
    // vector<string> input={"a", "b", "be", "bdd", "bde", "bdce", "bddce"};

    cout<<longestChain(input);

}

这个超时：

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;


int DFS(vector<string>& , string, unordered_map<string, int> & );

int longestChain(vector<string> &input){
    unordered_map<string, int> DP;
    for(auto e: input){
        DP[e]=0; // Initialize memo table.
    }

    int max_len=0;

    for(int i=0; i<input.size(); ++i){
        if(DP[input[i]]==0){
            max_len=max(max_len, DFS(input, input[i], DP));
        }
    }

    // for(auto e: DP){
    //     cout<<e.first<<' '<<e.second<<'\n';
    // }

    return max_len;
}

bool isValidChild(string a, string b){
    if(a.size()-b.size()!=1) return false;

    bool flag=false;

    for(int i=0; i<a.size(); ++i){
        string c(a);
        c.erase(i, 1);
        flag = flag || c==b;
    }

    return flag;
}

int DFS(vector<string>& input, string word, unordered_map<string, int> & DP){
    if(DP[word]!=0) return DP[word];

    if(word.size()==1){
        DP[word]=1;  // Single letter word, length == 1
        return 1;
    }

    int longest=0;

    for(int i=0; i<input.size(); i++){
        if(isValidChild(word, input[i])){
            longest = max(longest, DFS(input, input[i], DP));
        }
    }
    DP[word] = longest+1;
    return DP[word];

}

int main(){
    // int N=6;
    vector<string> input;
    input.push_back("a");
    input.push_back("e");
    input.push_back("be");
    input.push_back("bdc");
    input.push_back("bde");
    input.push_back("bdce");
    // input.push_back("efgh");

    cout<<longestChain(input);

}