Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

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

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "*") ? true
isMatch("aa", "a*") ? true
isMatch("ab", "?*") ? true
isMatch("aab", "c*a*b") ? false
C++:
01 void processNode(const char *s, const char*p,
02              vector<bool*>& A, int n, int m, int i, int j)
03 {
04     if(p[j]==‘?’)
05     {
06         A[i][j]=A[i+1][j+1];
07     }
08     else if(p[j]==‘*’)
09     {
10         for(int t=0;i+t<=n;t++)
11         {
12             if(A[i+t][j+1]==true)
13             {
14                 A[i][j]=true;
15                 return;
16             }
17         }
18     }
19     else if((s[i]==p[j])&&(A[i+1][j+1]==true))
20     {
21         A[i][j]=true;
22     }
23 }
24 class Solution {
25 public:
26      bool isMatch(const char *s, const char *p) {
27        int n=0;
28        int m=0;
29        int cnt=0;
30        for(int i=0;s[i]!=;i++,n++);
31        for(int i=0;p[i]!=;i++,m++)
32        {
33          if((p[i]>=‘a’)&&(p[i]<=‘z’))
34                cnt++;
35        }
36        if(cnt>n)
37            return false;
38        vector <bool*> A(n+1);
39        for(int i=0;i<=n;i++)
40        {
41            A[i]=new bool[m+1];
42            for(int j=0;j<=m;j++)
43               A[i][j]=false;
44        }
45        A[n][m]=true;
46        for(int i=m1;i>=0;i)
47        {
48            if((p[i]==‘*’)&&(A[n][i+1]==true))
49                A[n][i]=true;
50        }
51        for(int i=n1;i>=0;i)
52        {
53            for(int j=m1;j>=0;j)
54            {
55                processNode(s,p,A,n,m,i,j);
56            }
57        }
58        return A[0][0];
59  }
60 };
Advertisements
This entry was posted in Dynamic programming, String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s