. 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
  • $\begingroup$ We don't usually check solutions. That's your TA's job. $\endgroup$ Nov 6, 2017 at 7:50
  • $\begingroup$ @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. $\endgroup$ Nov 6, 2017 at 9:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.