Help needed in digit dp problem from today's leetcode contest.
Difference between en2 and en3, changed 18 character(s)
Problem -> [Problem](https://leetcode.com/problems/find-all-good-strings/)↵
↵
I am trying something similar to digit dp where we need to find the number of numbers in the range a to b satisfying some property, just in this case we have strings.↵
↵
My helper function is actually calculating the number of good strings which are lexicographically less than or equal **s** and do not contain the substring evil.↵
↵
Then I simply subtract the answer for two cases.↵
↵
Can someone please help me in this problem.↵
↵
<spoiler summary="Spoiler">↵
...↵
↵
↵
~~~~~↵
class Solution {↵
public:↵
    ↵
    long int dp[501][51][2];↵
    ↵
    const long int hell=1000000007;↵
    ↵
    long int helper(string &s,int st,bool flag,string s2,int p){↵
        if(p>=s2.length())↵
            return 0;↵
        if(st>=s.length())↵
            return 1;↵
        if(dp[st][p][flag]!=-1)↵
            return dp[st][p][flag];↵
        long int ans=0,np;↵
        for(char c='a';c<='z';c++){↵
            np=c==s2[p]?p+1:0;↵
            if(st==0){↵
                if(c>s[st])↵
                    break;↵
                if(c==s[st])↵
                    ans+=helper(s,st+1,true,s2,np);↵
                else↵
                    ans+=helper(s,st+1,false,s2,np);↵
            }↵
            else{↵
                if(flag){↵
                    if(c>s[st])↵
                        break;↵
                    else if(c==s[st])↵
                        ans+=helper(s,st+1,flag,s2,np);↵
                    else↵
                        ans+=helper(s,st+1,false,s2,np);↵
                }↵
                else↵
                    ans+=helper(s,st+1,false,s2,np);↵
            }↵
            ans%=hell;↵
        }↵
        return dp[st][p][flag]=ans;↵
    }↵
    ↵
    int findGoodStrings(int n, string s1, string s2, string evil) {↵
        if(s1>s2)↵
            return 0;↵
        long int ans1,ans2;↵
        memset(dp,-1,sizeof dp);↵
        ans2=helper(s2,0,false,evil,0);↵
        memset(dp,-1,sizeof dp);↵
        ans1=helper(s1,0,false,evil,0);↵
        long int c=0;↵
        if(s1.find(evil)==string :: npos)↵
            c=1;↵
        //cout<<ans2<<" "<<ans1<<" "<<ans2-ans1;↵
        return (ans2-ans1+c+hell)%hell;↵
    }↵
};↵
↵
~~~~~↵
</spoiler>↵
↵
 ↵
↵
This solution only passes 15 test cases.↵
↵
Someone please guidHelp me please.↵
↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Mikemirzyanov1 2020-04-12 11:46:24 47
en3 English Mikemirzyanov1 2020-03-31 12:02:37 18 Tiny change: 't cases.\n\nSomeone please guide.\n\n' -> 't cases.\nHelp me please.\n\n'
en2 English Mikemirzyanov1 2020-03-29 16:14:55 11 Tiny change: 'less than **s** and' -> 'less than or equal **s** and'
en1 English Mikemirzyanov1 2020-03-29 15:09:58 2369 Initial revision (published)