Regular Expression Matching
Implement 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
思路:
分两种状态。第一种状态是单个字符比较,第二种状态是带“*”的比较。状态通过预读pattern的下一个字符,判断是不是“*”来决定。
第一种状态下,如果遇到s结束,或者字符不同且pattern对应字符不是通配符“.”,则判定为不通过。否则读取字符串和pattern对应的下一个字符。
第二种状态则分两种情况:
- 因为"*"可以表示0个到多个元素,因此可以跳过"*"元素,直接用当前字符匹配下一个pattern元素。
- 在当前字符和当前pattern匹配的情况下,可以用当前pattern继续匹配。
在这里就用一个递归来处理。
题解:
class Solution { public: bool isMatch (const char* s, const char* p) { // invalid input? if (s == nullptr || p == nullptr) return false; // we loop to match every single character that is not regex while (true) { char s_ch = *s; char p_ch = *p; if (s_ch == 0 && p_ch == 0) return true; // reached the end, hurray~ if (p_ch == 0) return false; // premature of regular expression bool rep_flag = (* (p+1) == '*'); if (!rep_flag) { // characterwise comparison if (s_ch == 0 || (p_ch != '.' && s_ch != p_ch)) return false; // not matching // char match, continue ++p; ++s; } else { if (p_ch != '.' && s_ch != p_ch) // because * stands for "any", we can neglect this regex term return isMatch (s, p + 2); else { // it can match, but we can omit this term bool stat1 = isMatch (s, p + 2); bool stat2 = (s_ch == 0 ? false : isMatch (s + 1, p)); return stat1 | stat2; } } } } };