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


第一遍：

 1 public class Solution {
 2     public boolean isMatch(String s, String p) {
 3         if(p.length() == 0) return s.length() == 0;
 4         if(s.length() == 0) return p.length() == 0;
 5         if(p.charAt(0) == '?' || p.charAt(0) == s.charAt(0)) return isMatch(s.substring(1), p.substring(1));
 6         else if(p.charAt(0) == '*'){
 7             for(int i = 0; i < s.length(); i ++){
 8                 if(isMatch(s.substring(i), p.substring(1))) return true;
 9             }
10             return false;
11         }
12         else return false;
13     }
14 }

Time Limit Exceeded

"abbabbbaabaaabbbbbabbabbabbbabbaaabbbababbabaaabbab", "*aabb***aa**a******aa*"

网上做法：

贪心的策略，能匹配就一直往后遍历，匹配不上了就看看前面有没有'*'来救救场，再从'*'后面接着试。

 1 public class Solution {
 2     public boolean isMatch(String s, String p) {
 3         int i = 0;
 4         int j = 0;
 5         int star = -1;
 6         int mark = -1;
 7         while (i < s.length()){
 8             if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
 9                 ++i;
10                 ++j;
11             } else if (j < p.length() && p.charAt(j) == '*') {
12                 star = j++;
13                 mark = i;
14             } else if (star != -1) {
15                 j = star + 1;
16                 i = ++mark;
17             } else {
18                 return false;
19             }
20         }
21         while (j < p.length() && p.charAt(j) == '*') {// i == s.length()
22             ++j;
23         }
24         return j == p.length();
25     }
26 }

DP 解法：但是会memory limit exceeded：

 1 public class Solution {
 2     public boolean isMatch(String s, String p) {
 3         if(p == null || p.length() == 0) return s == null || s.length() == 0;
 4         if(s == null || s.length() == 0){
 5             return p == null || p.length() == 0 || (p.charAt(0) == '*' && isMatch(s, p.substring(1)));
 6         }
 7         int plen = p.length();
 8         int slen = s.length();
 9         boolean[][] dp = new boolean[plen][slen];
10         if(p.charAt(0) == s.charAt(0) || p.charAt(0) == '?' || p.charAt(0) == '*') dp[0][0] = true;
11         for(int i = 1; i < plen; i ++){
12             if(p.charAt(i) == '*') dp[i][0] = dp[i - 1][0];
13             else break;
14         }
15         for(int j = 1; j < slen; j ++){
16             if(p.charAt(0) == '*') dp[0][j] = dp[0][j - 1];
17         }
18         for(int i = 1; i < plen; i ++){
19             for(int j = 1; j < slen; j ++){
20                 if(p.charAt(i) == '?' || p.charAt(i) == s.charAt(j)) dp[i][j] = dp[i - 1][j - 1];
21                 else if(p.charAt(i) == '*'){
22                     dp[i][j] = dp[i - 1][j] || dp[i - 1][j - 1] || dp[i][j - 1];
23                 }else{
24                     dp[i][j] = false;
25                 }
26             }
27         }
28         return dp[plen - 1][slen - 1];
29     }
30 }

Time Limit Exceeded

相关推荐