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.↵
↵
↵
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 guid
↵