# LeetCode 10. Regular Expression Matching

xiaoxiao2021-02-28  4

## LeetCode 10. 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

## 代码实现

class Solution { public: bool isMatch(string s, string p) { //从后到前 匹配 s 和 p int index_p = p.size() - 1; int index_s = s.size() - 1; //mod == true 代表前一个是字母 //mod == false 代表前一个是* bool mod = true; while(index_s >= 0 && index_p >= 0) { if (mod) { if (s[index_s] == p[index_p] || p[index_p] == '.') { index_p--; index_s--; } else if (p[index_p] == '*') { mod = false; index_p--; if (isMatch(s.substr(0, index_s + 1), p.substr(0, index_p)))return true; } else return false; } else { if (s[index_s] == p[index_p] || p[index_p] == '.') { if ( isMatch(s.substr(0, index_s), p.substr(0, index_p)) )return true; index_s--; } else if (p[index_p] == '*')index_p--; else { mod = true; index_p--; } } } mod = false; while (index_p > index_s) { if ( p[index_p] == '*') { index_p--; mod = true; } else if (mod) { index_p--; mod = false; } else break; } return index_s == index_p; } };