DP hard Find All Good Strings digit DP

The last question of Leetcode weekly contest 182 is pretty hard.

1397. Find All Good Strings

Solution from

runtime in C++ 240 ms

const int mxN=500, mxM=50, M=1e9+7;
class Solution {

translate to python, runtime 3000+ ms

class Solution:
def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:
N, M = n, len(evil)
MOD = 10**9+7
dp = [[[0,0] for j in range(M+1)] for i in range(N+1)]
tr = [[0]*26 for _ in range(M+1)]
def solve(n, s, e):
e = e[::-1]
for i, c in enumerate(e):
f = e[:i]
for j in range(26):
g = f+chr(ord('a')+j)
for k in range(i+1, -1, -1):
if g[i+1-k:]==e[:k]:
tr[i][j] = k
break
for i in range(N+1):
for j in range(M+1):
dp[i][j] = [0, 0]
dp[N][0][1] = 1
for i in range(n-1, -1, -1):
for j in range(len(e)):
for k in range(26):
for l in range(2):
nl = 0
if k<ord(s[i])-ord('a'):
nl = 1
elif k>ord(s[i])-ord('a'):
nl = 0
else:
nl = l
dp[i][tr[j][k]][nl]=(dp[i+1][j][l]+dp[i][tr[j][k]][nl])%MOD
return sum(dp[0][j][1] for j in range(len(e)))%MOD
ans = solve(n, s2, evil)
if set(s1)=={'a'}:return ans
s1 = list(s1)
for i in range(n-1,-1,-1):
if s1[i]>'a':
s1[i] = chr(ord(s1[i])-1)
break
s1[i] = 'z'
s1 = ''.join(s1)
ans1 = solve(n, s1, evil)
return (ans+MOD-ans1)%MOD

Some other solutions by using KMP

Aoxiang cui’s it is only 44 ms. It is kind of faster.

const int MOD = 1e9 + 7;
const int N = 500 + 10;
const int M = 50 + 10;
int dp[N][M][2];

Python solution from this link, it is only 904 ms. It is also faster.

https://leetcode.com/problems/find-all-good-strings/discuss/555010/Python-Simple-DFS-with-KMP

from functools import lru_cache

Reference

https://www.geeksforgeeks.org/digit-dp-introduction/

https://oi-wiki.org/dp/number/

Data Scientist/MLE/SWE @takemobi