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 bool isMatch(const char *s, const char *p) {
02       int n=0;
03       int m=0;
04       int cnt=0;
05       for(int i=0;s[i]!=;i++,n++);
06       for(int i=0;p[i]!=;i++,m++){
07           if((p[i]>=‘a’)&&(p[i]<=‘z’))
08               cnt++;
09       }
10       if(cnt>n)
11           return false;
12       bool A[n+1][m+1];
13       for(int i=0;i<=n;i++)
14           for(int j=0;j<=m;j++)
15              A[i][j]=false;
16       A[n][m]=true;
17       for(int i=n1;i>=0;i)
18           A[i][m]=false;
19       for(int i=m1;i>=0;i){
20           if((p[i]==‘*’)&&(A[n][i+1]==true))
21               A[n][i]=true;
22           else
23               A[n][i]=false;
24       }
25       for(int i=n1;i>=0;i){
26           for(int j=m1;j>=0;j){
27               if(((s[i]==p[j])||(p[j]==‘?’))&&
28                  (A[i+1][j+1]==true)){
29                   A[i][j]=true;
30                     continue;
31               }
32               if(p[j]==‘*’){
33                   for(int t=i;t<=n;t++){
34                       if(A[t][j+1]==true){
35                           A[i][j]=true;
36                           break;
37                       }
38                   }
39               }
40           }
41       }
42       return A[0][0];
43 }
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