传送门：https://leetcode-cn.com/problems/regular-expression-matching/

题目

给你一个字符串s和一个字符规律p，请你来实现一个支持'.' 和'*'的正则表达式匹配。

'.' ：匹配任意单个字符 '*' ：匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。

示例 1：

输入：s = “aa” p = “a” 输出：false 解释：”a” 无法匹配 “aa” 整个字符串。


示例 2:**

输入：s = “aa” p = “a“ 输出：true 解释：因为 ‘‘ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。


示例 3：**

输入：s = “ab” p = “.“ 输出：true 解释：”.“ 表示可匹配零个或多个（’*’）任意字符（’.’）。


示例 4：**

输入：s = “aab” p = “cab” 输出：true 解释：因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5：

输入：s = “mississippi” p = “misisp*.” 输出：false

阿巴阿巴 ….大家好，我是老实巴交的老实人，得知大家都用动态规划做的我人傻了。

代码

我的代码

  1. class Solution {
  2. public:
  3. bool clearOne(string p) {//空串返回false
  4.     int p_len = p.length();
  5.     int pp = 0;
  6.     if (p.empty() || p == "")return false;
  7.     if (((pp + 1) < p.length()) && (p.at(pp + 1) == '*')) return true;
  8.     return false;
  9. }
  10. bool check_pnull(string p) {//判断规则p剩余部分是否可以抵消
  11.     int p_len = p.length();
  12.     int pp = 0;
  13.     if (p.empty() || p == "")return true;
  15.     while (pp < p_len) {//字母在
  16.         if (pp + 1 < p_len) {//*号在
  17.             if (p.at(pp + 1) == '*')//*匹配
  18.                 pp += 2;
  19.             else
  20.                 return false;
  21.         }
  22.         else {//*号不在
  23.             if (p.at(pp) == '*')
  24.                 return true;
  25.             return false;
  26.         }
  27.     }
  28.     return true;
  29. }
  31. bool isMatch(string s, string p) {
  32.     int s_len = s.length();
  33.     int p_len = p.length();//二者长度
  34.     int sp, pp;//哨兵
  35.     sp = pp = 0;//初始化
  36.     if ((!s.empty()) && (p.empty() || p == ""))return false;
  37.     if (!p.empty() && (s.empty() || s == "")) {
  38.         if (check_pnull(p))return true;
  39.         return false;
  40.     }//去除非法情况和特殊空串情况
  41.     while (sp < s_len || pp < p_len) {
  42.         while ((sp < s_len && pp < p_len) && s.at(sp) == p.at(pp)) {//二者相等就顺着排
  43.             sp++; pp++;
  44.         }//匹配就下行
  45.         //出来有可能是不匹配也有可能是超过长度
  46.         //1不匹配
  47.         if (sp < s_len && pp < p_len) {//确保在长度内
  48.             if (p.at(pp) == '.') {//.类型不匹配
  49.                 sp++; pp++;
  50.             }
  51.             else if (p.at(pp) == '*') {//*类型不匹配
  52.                 bool real = false;
  53.                 int temp_sp = sp - 1;
  54.                 //第一种先消去*前面的来跟s匹配
  55.                 if (pp + 1 < p_len)//未越界情况才有可能消去，越界一定不用消除
  56.                     real= isMatch(s.substr(temp_sp, s_len - temp_sp), p.substr(pp + 1, p_len - pp - 1));
  57.                 if (real)return true;
  58.                 //第二种到底匹配几个的问题 
  59.                 if ((sp < s_len && pp + 1 < p_len)) {//*只匹配一次
  60.                     real = isMatch(s.substr(sp, s_len - sp), p.substr(pp + 1, p_len - pp - 1));
  61.                     if (real)return true;
  62.                 }
  63.                 while ((sp < s_len && pp < p_len)) {//从第2此开始依次匹配
  64.                     if ((s.at(sp) == p.at(pp - 1)) || p.at(pp - 1) == '.') {
  65.                         sp++;
  66.                         if ((sp < s_len && pp + 1 < p_len)) {
  67.                             real = isMatch(s.substr(sp, s_len - sp), p.substr(pp + 1, p_len - pp - 1));
  68.                             if (real)return true;
  69.                         }
  70.                     }
  71.                     else {
  72.                         pp++;
  73.                         break;
  74.                     }
  75.                 }
  76.             //    pp++;
  77.             }
  78.             else {
  79.                 if ((pp + 1 < p_len) && (p.at(pp + 1) == '*')) {//还有救
  80.                     pp += 2;
  81.                 }
  82.                 else
  83.                     return false;
  84.             }
  86.         }
  87.         else {//2超出长度
  88.                 //如果二者同时超出了长度则说明匹配成功
  89.                 //若是单独一方超出则要看情况
  90.                 //a. 若p超出了长度，说明s串还有未比配的数，一定不匹配
  91.                 //b. 若s超出了长度，说明要回溯，两种检查，剩下p是否能check_pnull，若能则匹配，若不能则claenOne弄掉一对让s的最后一个字母与剩下的p规则匹配
  92.             if (sp == s_len && pp == p_len) {//二者同时超出了长度则说明匹配成功
  93.                 return true;
  94.             }
  95.             else {//单独一方超出
  96.                 if (pp >= p_len)return false;//a
  97.                 if (sp >= s_len) {//b
  98.                     if (p.at(pp) == '*') {
  99.                         if (check_pnull(p.substr(pp + 1, p_len - pp))) return true;//剩下的能消除
  100.                         else {//不能消除
  101.                             if (clearOne(p.substr(pp - 1, p_len - pp + 1))) {
  102.                                 sp--;
  103.                                 pp = pp + 1;
  104.                                 return isMatch(s.substr(sp, s_len - sp), p.substr(pp, p_len - pp));
  105.                             }
  106.                             else return false;
  107.                         }
  108.                     }
  109.                     else {
  110.                         if (check_pnull(p.substr(pp, p_len - pp))) return true;//剩下的能消除
  111.                         else {//不能消除
  112.                             if (clearOne(p.substr(pp - 1, p_len - pp + 1))) {
  113.                                 sp--;
  114.                                 pp = pp + 1;
  115.                                 return isMatch(s.substr(sp, s_len - sp), p.substr(pp, p_len - pp));
  116.                             }
  117.                             else return false;
  118.                         }
  119.                     }
  120.                 }
  121.             }
  122.         }    
  123.     }
  124.     if (sp == s_len && pp == p_len)
  125.         return true;
  126.     else
  127.         return false;
  128. }
  129. };