Leetcode 1048. Longest String Chain || DP

Problem Link

In this problem, there will be given array of words consisting of lowercase English letters. We have to find the longest chain of word we can make from these words. A chain between two words can make if and only if deleting only single character from one of the word makes other one. In example,
abcde->abde , abcde->bcde can have chain between them. But, abcde->adce cant.
Now, we have to find the longest chain length we can make  from these words.

Idea: Instead of making words from smaller word, we can find a smaller word from a bigger one. For this purpose,
1.We first generated all the word(size == original word size -1) from a given word and,
2.we tested which generated word is belongs to the words array. If any word is found repeat step 1-2.

So, it seems going for the all possible case we can generate  so far. But doing it in recursive naive approach surely will exceed the time limits. So, we need to use memoization.

Code[ Memoization]:

class Solution {
public:
    unordered_map<string,int>wordMap,memo;
    int ans=1;
    int caller(string str){
        if(str.size()==1){
            if(wordMap[str]!=0) memo[str]=1;
            else memo[str]=0;
            return memo[str];
        }
        if(wordMap[str]==0){
            memo[str] = 0;
            return 0;
        }
        else if(wordMap[str]!=0){
            for(int j=0;j<str.size();j++){
                string temp = str.substr(0,j) + str.substr(j+1,str.size()-j);
                if(memo[temp]==0){
                    memo[str] = max(memo[str],caller(temp)+1);
                }
                else memo[str] = max(memo[str],memo[temp]+1);
            }
        }
        return memo[str];
    }
    int longestStrChain(vector<string>& words) {
        for(int i=0;i<(int)words.size();i++){
            wordMap[words[i]]++;
        }
        for(int i=0;i<(int)words.size();i++){
            if(memo[words[i]]==0){
                memo[words[i]]=caller(words[i]);
            }
            ans = max(ans,memo[words[i]]);
        }
        return ans;
    }
};