《剑指offer》【剑指 Offer 19. 正则表达式匹配】

目录

💎一、题目

🏆1.题目描述

🏆2.原题链接

💎二、解题报告

🏆1.思路分析

🏆2.代码详解

---

💎一、题目

🏆1.题目描述

 

🏆2.原题链接

剑指 Offer 19. 正则表达式匹配

💎二、解题报告

🏆1.思路分析

🔑思路：

第一个情况，两者相等，则都往后移动一位，

第二个情况，"."可以代替任何字符，所以都往后移动一位，

第三种情况，"*"之前字符和i字符相等，1.认为"*"相当0个a则j向后移动两位2.认为"*"相当1个a则i向后移动一位，j向后移动一位3.认为"*"相当多个a，则j不变则i向后移动一位，

第四种情况，当遇到"*"前是"."和第三种情况一样，

第五种情况，"*"之前字符和i字符不相等，则认为"*"相当于0个a，则j向后移动两位

🏆2.代码详解

class Solution {
public:
    bool isMatch(string s, string p) {
        if(s.size() == 0 && p.size() == 0) return true;
        if(s.size() != 0 && p.size() == 0) return false;
        return isMatchcore(s, 0, p, 0);                    //1
    }
    bool isMatchcore(string& s, int i, string& p, int j)
    {
        if(s.size() == i && p.size() == j) return true;    //2
        if(s.size() > i && p.size() == j) return false;
        if(p[j+1] == '*')                                    //3
        {
            if(s[i] == p[j] || (p[j] == '.' && i < s.size()))//4
            {
                return isMatchcore(s, i, p, j+2)
                    || isMatchcore(s, i+1, p, j+2)
                    || isMatchcore(s, i+1,p, j);
            }
            else                                            //5
            {
                return isMatchcore(s, i, p, j+2);
            }
        }
        if(s[i] == p[j] || (p[j] == '.' && i < s.size()))    //6
            return isMatchcore(s, i+1,p, j+1);
        return false;
    }
};

1.传入字符串和起始位置
2.都走完了返回true， s没有走完但p匹配完了，返回false
3.遇到"*"
4.遇到的位置当前相等或是"."
5.遇到的位置当前不等
6.遇到"."或者相等