https://leetcode.com/problems/regular-expression-matching/description/

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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("aab", "c*a*b") → true

• 字符串匹配。最后一个样例中匹配是因为*可以是0次匹配，i.e. c0a2b。
• 递归法或者动态规划。

1 // 2 //  main.cpp 3 //  LeetCode 4 // 5 //  Created by Hao on 2017/3/16. 6 //  Copyright © 2017年 Hao. All rights reserved. 7 // 8  9 #include 
      
       10 #include 
       
        11 using namespace std;12 13 class Solution {14 public:15     bool isMatch(string s, string p) {16         return isMatch(s.c_str(), p.c_str());17     }18 19 private:20     bool isMatch(const char *s, const char *p) {21         if (*p == '\0') return *s == '\0';22         23         // next char is not '*', must match the current char24         if (*(p + 1) != '*') {25             if ((*p == *s) || ((*p == '.') && (*s != '\0')))26                 return isMatch(s + 1, p + 1);27             else28                 return false;29         } else { // next char is '*'30             // '*' matches zero or more of the preceding element31             while ((*p == *s) || ((*p == '.') && (*s != '\0'))) {32                 // check if the remaining string matches33                 if (isMatch(s, p + 2))34                     return true;35                 // move point36                 s ++;37             }38             // next matching39             return isMatch(s, p + 2);40         }41     }42 };43 44 int main ()45 {46     Solution testSolution;47     string sTest[] = {
    "aa", "a", "aa", "aa", "aaa", "aa", "aa", "a*", "aa", ".*", "ab", ".*", "aab", "c*a*b"};48 49     for (int i = 0; i < 7; i ++)50         cout << testSolution.isMatch(sTest[2 * i], sTest[2 * i + 1]) << endl;51     52     return 0;53 }