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.递归-->超时
/* p的任何一个位置，字符有三种可能 1.？：只能匹配当个字符 2.*：可以匹配任意字符 3.处理？和*的任意字符 可以使用递归： s[i]和p[j]匹配，则继续匹配下一位置 s[i]和p[j]不匹配，返回假 特殊情况： 1.s到了末尾，p未到末尾，需要检查p剩余的字符是否含有除*外的其他字符 2.s未到末尾，p到了末尾，返回假 3.s到了末尾，p到了末尾，返回真 */ class Solution { public: bool isMatch(string s,int startS,string p,int startP) { int sSize = s.size(); int pSize = p.size(); if(startS < sSize && startP < pSize){ if(s[startS]==p[startP] || p[startP]==‘?‘){ return isMatch(s,startS+1,p,startP+1); } if(p[startP]==‘*‘){ return isMatch(s,startS+1,p,startP) || isMatch(s,startS,p,startP+1) || isMatch(s,startS+1,p,startP+1); } return false; }else if(startS==sSize && startP<pSize){ for(int i=startP;i<pSize;i++){ if(p[i]!=‘*‘){ return false; } } return true; }else if(startS<sSize && startP==pSize){ return false; }else{ return true; } } bool isMatch(string s, string p) { return isMatch(s,0,p,0); } };
原文：http://www.cnblogs.com/zengzy/p/5019079.html