Skip to content

Instantly share code, notes, and snippets.

@maksadbek
Last active July 9, 2020 08:41
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save maksadbek/a687c9f4cd8ef496b45b05ebb070d92a to your computer and use it in GitHub Desktop.
def tushar(string, pattern):
dp = [[False] * (len(pattern) + 1) for _ in range(len(string) + 1)]
dp[0][0] = True
for i in range(1, len(pattern)+1):
if pattern[i-1] == "*":
dp[0][i] = dp[0][i-2]
for i in range(1, len(string)+1):
for j in range(1, len(pattern)+1):
match = pattern[j-1] in [string[i-1], "."]
if match:
dp[i][j] = dp[i-1][j-1]
elif pattern[j-1] == "*":
dp[i][j] = dp[i][j - 2]
if pattern[j-2] in [string[i-1], "."]:
dp[i][j] = dp[i][j] or dp[i-1][j]
else:
dp[i][j] = False
return dp[len(string)][len(pattern)]
print(tushar("aab", "a*b"))
print(tushar("aa", "a"))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment