[題目] 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
[中文翻譯] 實現(xiàn)正則表達式匹配，支持’.’和’*’。
‘.’ 匹配任何單個字符. ‘*’ 匹配0個或多個前導(dǎo)字符.
需要匹配整個輸入的字符串（不是部分）.
函數(shù)原型如下: 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
[解題思路] 普通的字符就一一匹配。 ‘.’比較好處理，匹配任意字符。 麻煩的是’*’，使用遞歸，依次枚舉’*’所代表的個數(shù)。
思路大致如此，代碼實現(xiàn)地比較煩，是我很早以前寫的，又沒有寫注釋。 最近很煩，也不想補注釋了，諒解。
[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; } }};新聞熱點
疑難解答
