1
$\begingroup$

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[0][0] = true since an empty string matches an empty pattern.

-dp[0][j] = dp[0][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[0][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[0][0] = true

For j = 1 to pLen

          If P[j] = ‘*’

                   dp[i][j] = dp[0][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

abcccdeeef

and string

abcdcccccdefefeefeeef

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.

$\endgroup$
  • $\begingroup$ "However, for his specific question..." -- I don't see a specific question at all. Could you clarify what exactly is your question? If his question was "have you thought of case x", your reply should be "yes, the proof is blah" and so on, right? $\endgroup$ – Juho Oct 14 at 19:36
  • $\begingroup$ @Juho I have edited the post, hopes it is clearer now $\endgroup$ – amV Oct 14 at 21:06

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.