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.按照剑指offer上的思路，用递归
class Solution { public: bool matchstr(string str, string pattern, int i, int j){ if(str.size() == i && pattern.size() == j) return true; if(str.size() == i || pattern.size() == j) return false; if(pattern[i+1] == '*'){ if(str[i] == pattern[j] || (pattern[i] == '.' && i < str.size())) return matchstr(str, pattern, i+1, j+2) ||matchstr(str, pattern, i+1, j) || matchstr(str, pattern, i, j+2); else return matchstr(str, pattern, i, j+2); } if(str[i] == pattern[j] || (pattern[i] == '.' && i < str.size())) return matchstr(str, pattern, i+1, j+1); return false; } bool isMatch(string s, string p) { if(s.size() == 0 && p.size() == 0) return true; if(s.size() == 0 || p.size() == 0) return false; return matchstr(s, p, 0, 0); } };
