[题目] mplement regular exPRession matching with support for ‘.’ and ‘*’.
‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element.
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”, “a*”) → true isMatch(“aa”, “.*”) → true isMatch(“ab”, “.*”) → true isMatch(“aab”, “c*a*b”) → true
[中文翻译] 实现正则表达式匹配，支持’.’和’*’。
‘.’ 匹配任何单个字符. ‘*’ 匹配0个或多个前导字符.
需要匹配整个输入的字符串（不是部分）.
函数原型如下: bool isMatch(const char *s, const char *p)
例子: isMatch(“aa”,”a”) → false isMatch(“aa”,”aa”) → true isMatch(“aaa”,”aa”) → false isMatch(“aa”, “a*”) → true isMatch(“aa”, “.*”) → true isMatch(“ab”, “.*”) → true isMatch(“aab”, “c*a*b”) → true
[解题思路] 普通的字符就一一匹配。 ‘.’比较好处理，匹配任意字符。 麻烦的是’*’，使用递归，依次枚举’*’所代表的个数。
思路大致如此，代码实现地比较烦，是我很早以前写的，又没有写注释。 最近很烦，也不想补注释了，谅解。
[C++代码]
class Solution {private: string ts, tp; int slen, plen;public: bool isMatch(string s, string p) { ts = s; tp = p; slen = s.size(); plen = p.size(); return myMatch(0, 0); } bool myMatch(int ps, int pp) { if (ps == slen && pp == plen) return true; if (ps < slen && pp == plen) return false; if (pp + 1 < plen) { if ('*' == tp.at(pp + 1)) { for (int i = ps; i < slen; i++) { if (ts.at(i) == tp.at(pp) || '.' == tp.at(pp)) { if (myMatch(i + 1, pp + 2)) return true; } else break; } return myMatch(ps, pp + 2); } else { if (ps == slen) return false; if (ts.at(ps) == tp.at(pp) || '.' == tp.at(pp)) return myMatch(ps + 1, pp + 1); else return false; } } else { if (ps == slen) return false; if (ts.at(ps) == tp.at(pp) || '.' == tp.at(pp)) return myMatch(ps + 1, pp + 1); else return false; } }};新闻热点
疑难解答
