leetcode_1048. Longest String Chain_[DP，动态规划，记忆化搜索]

1048. Longest String Chain

https://leetcode.com/problems/longest-string-chain/

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.

解法：动态规划

对于任意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(, vector<string>());

        for(auto word:words)

            len_word[word.size()].push_back(word);

        map<string,int> dp;

        int res=;

        for(int i=;i>=;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()-])

            Set.insert(word);

        int nowres=;

        for(int i=; i<nowword.size(); i++)

        {

            string temp=nowword;

            temp.erase(i,);

            if(Set.count(temp))

                nowres = max(nowres,dfs(len_word,temp,dp)+);

        }

        return dp[nowword]=nowres;

    }

};

巴特西

leetcode_1048. Longest String Chain_[DP，动态规划，记忆化搜索]

最新文章

热门文章