【剑指Offer】正则表达式匹配（思路清晰）

题目重述：

请实现一个函数用来匹配包括’.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配

思路：

首先看到这个题我们要考虑到用递归较容易，思路比较清晰。 （大家也可以尝试非递归，说不定我后面会写，用一个二维字符串组来存储结果，可以试一下非递归，我估计有文章会写这个题，也算是对动态规划的练习）

1》》一说 到递归，我们先考虑出口： （1）字符串str 和模式pattern都走到了最后的‘’处，说明全匹配，返回true. （2）字符串str还未到’’处，但是pattern已经到了‘’处，说明不匹配，返回false。

现在我们考虑什么时候该怎么调用：（这块参考牛客第一个java写的经典思路）

2》》当模式中的第二个字符不是“*”时：

（1）如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。

（2）如果 字符串第一个字符和模式中的第一个字符相不匹配，说明存在不匹配项，直接返回false。

3》》而当模式中的第二个字符是 ‘※’ 时：

（1）如果字符串第一个字符跟模式第一个字符匹配，可能有3种匹配方式： 1>模式后移2字符，相当于x※被忽略； 2>字符串后移1字符，模式后移2字符； （这个第二个方式，如果你看的比较懂，其实可以让1>和3>组合代替，先3>再1> 就可代替2>。但是写着的话，更清晰。） 3>字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位； （2）如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。

代码

class Solution {
          
   
public:
    bool match(char* str, char* pattern)
    {
          
   
    	//出口（1）
        if (*str ==  && *pattern == )
            return true;
        //出口（2）
        if (*str !=  && *pattern == )
            return false;
        //当模式中的第二个字符不是“*”时；
        if (*(pattern + 1) != *) {
          
   
            //（1）str与pattern匹配。
            if (*str == *pattern || (*str !=  && *pattern == .))
                return match(str + 1, pattern + 1);
            //（2）str与pattern 有不匹配的项了，直接返回false。题目要求全匹配
            else
                return false;
        }
        //而当模式中的第二个字符是 ‘*’ 时
        else {
          
   
        //（1）如果字符串第一个字符跟模式第一个字符匹配，可能有3种匹配方式：
            if (*str == *pattern || (*str !=  && *pattern == .))
                return match(str, pattern + 2)||//1>模式后移2字符，相当于x※被忽略；
                match(str + 1, pattern + 2) || //2>字符串后移1字符，模式后移2字符；
                match(str + 1, pattern);//3>字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；

            //（2）如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。
            else
                return match(str, pattern + 2);
        }
    }
};