【leetcode刷题笔记】Wildcard Matching

‘?‘ 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

 1 public class Solution {
 2     public boolean isMatch(String s, String p) {
 3         int m = s.length();
 4         int n = p.length();
 5         
 6         int count = 0;
 7         for(int indexP = 0;indexP<n;indexP++)
 8             if(p.charAt(indexP) != ‘*‘)
 9                 count++;
10         if(count > m)
11             return false;
12         
13         boolean[][] dp =new boolean[m+1][n+1];
14         dp[0][0] = true;
15         
16         for(int j = 1;j<=n;j++)
17         {   
18             char ch_p = p.charAt(j-1);
19             if(ch_p ==‘*‘ && dp[0][j-1])
20                 dp[0][j]= true;
21             
22             for(int i= 1;i<=m;i++){
23                 char ch_s = s.charAt(i-1);
24                 if(ch_p ==‘*‘)
25                     dp[i][j]= dp[i-1][j]|| dp[i][j-1];
26                 else if(ch_p == ‘?‘ || ch_p == ch_s){
27                     dp[i][j] = dp[i-1][j-1]; 
28                 }
29                 else
30                     dp[i][j]= false; 
31             }
32         }
33         return dp[m][n];
34     }
35 }