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 }
"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 }
Wildcard Matching,布布扣,bubuko.com
原文：http://www.cnblogs.com/reynold-lei/p/3921872.html