题目：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
解析一：用递归方法：
代码参考了网址https://github.com/soulmachine/leetcode#leetcode题解题目
// 递归算法// 时间复杂度O(n!*m!)，空间复杂度O(n)class Solution {public: bool isMatch(string s, string p) { return isMatch(s.c_str(), p.c_str()); }private: bool isMatch(const char* s, const char* p) { if (*p == '/0') return *s == '/0'; if (*p != '*') { if (*p == *s || *p == '?' && *s != '/0') return isMatch(s + 1, p + 1); else return false; } else { while (*p == '*') ++p; // skip continuous '*' if (*p == '/0') return true; while (*s != '/0') { if (isMatch(s, p)) return true; ++s; } return false; } }};解析二：迭代版。
代码参考了网址http://www.cnblogs.com/felixfang/p/3708999.html
class Solution {public: bool isMatch(const string& s, const string& p) { return isMatch(s.c_str(), p.c_str()); }private: bool isMatch(const char* s, const char* p) { // previous starting comparsion place after * in s and p string const char *presp = nullptr, *press = nullptr; bool startFound = false; while (*s != '/0') { if (*p == '?') ++s, ++p; else if (*p == '*') { presp = ++p; press = s; startFound = true; } else { if (*p == *s) ++p, ++s; else if (startFound) p = presp, s = ++press; else return false; } } while (*p == '*') ++p; return *p == '/0'; }};新闻热点
疑难解答
