0
$\begingroup$

. 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
$\endgroup$
  • $\begingroup$ We don't usually check solutions. That's your TA's job. $\endgroup$ – Yuval Filmus Nov 6 '17 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$ – noman pouigt Nov 6 '17 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.