# Recurrence relation for a star and a dot wildchar pattern

. Matches any single character, * Matches any sequence of characters (including the empty sequence).

dict = ["cat", "cats", "and", "sand", "dog"].

pattern = "* t", -> true (can match cat)

pattern = ".a *" -> true (can match cat, cats, can also match sand, because * can also express empty sequence)

Is below recurrence relation captures the solution correctly?

DP[i][j] = True if i characters of string matches with j characters of pattern

DP[len(string)+1][len(pattern)+1] = False
DP[0][0] = True
DP[i][j] = DP[i-1][j]  if pattern[i] == "*"
DP[i-1][j-1] if pattern[i] == "."
DP[i-1][j-1] if (string[i] == pattern[j]) == any character

• We don't usually check solutions. That's your TA's job. – Yuval Filmus Nov 6 '17 at 7:50
• @YuvalFilmus: Thanks but I am not a student unfortunately. I have done the recursive solution for the same but I am stuck with my iterative solution. – noman pouigt Nov 6 '17 at 9:15