This is a wildcard matching problem. Given a pattern P containing letters and character * that can match an arbitrary string of characters (including an empty string), my task is to write a polynomial-time algorithm to determine whether such a pattern P occurs in a given text T. So here is my answer for the problem.
We can use dynamic programming to solve this problem. Let us have a 2D boolean array dp[i][j]. dp[i][j] returns true if there is a match between the pattern and the string. Initialize dp[i][j] = false -dp = true since an empty string matches an empty pattern. -dp[j] = dp[j-1] (= true) if P[j] = * for 1<= j <=m since an empty string matches ‘*’ as long as previous characters match. In other words, once P[j-1] != “*”, dp[j] will be false afterwards. -If P[j] = ‘*’, we have dp[i][j] = dp[i-1][j] || dp[i][j-1] For dp[i-1][j], ‘*’ acts as an empty string. E.g. ab and ab* For dp[i]p[j-1], ‘*’ acts as any sequences. E.g. abcd and ab* In other words, if P[j] = ‘*’ and (dp[i-1][j] || dp[i][j-1]) = true, dp[i][j] = true -If P[j] = T[i], it boils down to match T(i-1) and P(j-1). dp[i][j] = dp[i-1][j-1] For other cases, dp[i][j] is false. Pseudocode: tLen = T.length pLen = P.length Initialize dp[tLen+1][pLen+1] = false Dp = true For j = 1 to pLen If P[j] = ‘*’ dp[i][j] = dp[j-1] for i =1 to tLen for j=1 to pLen if P[j] = ‘*’ dp[i][j] = dp[i][j-1] or dp[i-1][j] else if P[j] = T[i] dp[i][j] = dp[i-1][j-1] else dp[i][j] = false Return dp[tLen][pLen] The algorithm fills a tLen x pLen table, so the running time is O(nm)
During a discussion in class, my professor said my answer is vague. He asked me if I had considered * can appear in the middle of the pattern and it can appear several times in the pattern. In particular, consider pattern
How does this algorithm determine, which c in the pattern should match with which c in the text? How does it with e?
My understanding towards this problem is that what matters is the final result of dp[tLen][pLen] and we use a table to compare substrings with each other.The character * would probably match any character it encounters. We just derive our answers from previous steps to fill out the whole table so that we can get the final result of dp[tLen][pLen]. However, for his specific question (that is, How does this algorithm determine, which c in the pattern should match with which c in the text? How does it with e?), I can't think of a reasonable way to answer. Any help with the explanation would be appreciated.