Longest String Chain Leetcode

#1

Problem link>


My code is working properly BUT I am not happy with extra O(n) space used IN SET can I optimize space somehow so that I DONT NEED SET using DP array instead of set???
MY code>>>>

#2

hello @joshisanjay8467
using bottom up we can eliminate the need of extra set.

in that case intilaise ur dp map with 1 for each string.

then iterate from i=0 to i<n
and update
dp[i]=max(dp[i],1 +dp[smallerpart])

  bool static cmp(string &s1,string &s2){
        return s1.size() <s2.size();
    }
    int longestStrChain(vector<string>& words) {
        map<string,int> dp;
      sort(words.begin(),words.end(),cmp);
        for(auto k : words)
              dp[k]=1;
        int ans=1;
        for(auto k : words){
            for(int i=0;i<k.size();i++){
                string a,b,s;
                s=k.substr(0,i)+k.substr(i+1);
                if(dp.count(s)){
                    dp[k]=max(dp[k],1+dp[s]);
                    ans=max(ans,dp[k]);
                }
              
                
            }
        }
        return ans;
    }
#3

well I only use top down based approach . Bottom up never makes sense to me . But for this one I got it. Top down is easy and intuitive just do recursion then memoize it

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.