题目链接

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

思路

image.png

整体递归

判等条件 s[i] == p[j] || p[j] == '.'
如果s[i] == p[j] || p[j] =='.',继续进行下一轮迭代，isMatch(s,j,i+1,j+1)
特殊情况"",当p.length >= 2时，（这里可以用s=aab,p=cdb例子来看）
p[1] != '' ，若判定s[i] == p[j] || p[j] =='.' ，继续i+1,j+1的迭代
p[1] =='*'，若判定s[i] == p[j] || p[j] =='.' ，如果isMatch($s,$p,$i,$j+2),可以继续迭代，否则$i++

class Solution {

    /**
     * @param String $s
     * @param String $p
     * @return Boolean
     */
    function isMatch($s, $p) {
        if(!$s){
            return false;
        }
        $s = str_split($s);
        $p = str_split($p);
        return $this->helper($s, $p, 0, 0);
    }

    function helper($s, $p, $i, $j) {

        //p下标对应的子串长度为0
        if ($j == count($p)) {
            return $i == count($s);
        }

        //p下标对应的子串长度为1
        if ($j == (count($p) - 1) || $p[$j + 1] != "*") {//p的下一个字符为*
            if ($i == count($s)|| $s[$i] != $p[$j] && $p[$j] != ".") {
                return false;
            }

            return $this->helper($s, $p, $i + 1, $j + 1);
        }

        //p下标对应的子串长度大于等于2
        //并且 划重点$p[$i+1] == "*"
        while ($i < count($s) && ($s[$i] == $p[$j] || $p[$j] == ".")) {
            //这里如果看不懂，可以用s=aab,p=c*a*b 这个例子走一遍
            if ($this->helper($s, $p, $i, $j + 2)) {
                return true;
            }
            $i++;
        }
        return $this->helper($s, $p, $i, $j + 2);
    }

}

参考：https://www.jianshu.com/p/85f3e5a9fcda
参考：https://blog.csdn.net/linhuanmars/article/details/21145563