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

题目

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

解题思路

每次从字符串中取出一个字符与模式进行匹配。

• 如果模式字符是 .，则字符匹配
• 如果模式字符 == 字符串字符，则字符匹配
• 如果下一个模式字符不是 *，则当字符匹配时字符串字符和模式字符都移动到下一个字符进行比较，不匹配则返回false
• 如果下一个模式字符是 *，当匹配时会出现两种情况，如下图状态转换
  • 匹配字符向后移动两个字符
  • 匹配字符不向后移动

graph LR
A-->|b|B
B-->|a|B
B-->|a|C

代码实现

<?php
function match($str, $pattern)
{
    if (empty($str) && empty($pattern)) {
        return false;
    }

    return matchCore($str, $pattern, 0, 0);
}

function matchCore($str, $pattern, $strIdx, $patternIdx)
{
    if ($strIdx >= strlen($str)) {
        $sChar = null;
    } else {
        $sChar = $str[$strIdx];
    }
    if ($patternIdx >= strlen($pattern)) {
        $pChar = null;
    } else {
        $pChar = $pattern[$patternIdx];
    }

    if (empty($sChar) && empty($pChar)) {
        return true;
    }
    if (!empty($sChar) && empty($pChar)) {
        return false;
    }

    // 下一个字符是不是 *
    if ($patternIdx + 1 >= strlen($pattern)) {
        $pNextChar = null;
    } else {
        $pNextChar = $pattern[$patternIdx + 1];
    }
    if ($pNextChar == '*') {
        // 字符匹配，且下一个字符是 *
        if ($pChar == $sChar || ($pChar == '.' && !empty($sChar))) {
            // 字符串字符后移一个，模式字符后移两个，跳过*
            return matchCore($str, $pattern, $strIdx + 1, $patternIdx + 2)
                // 字符串字符后移一个，模式字符不变，看下一个字符是否还能匹配模式字符
                || matchCore($str, $pattern, $strIdx + 1, $patternIdx)
                // 字符串字符不变，模式字符后移两个，跳过 *，忽略当前模式字符和 *
                || matchCore($str, $pattern, $strIdx, $patternIdx + 2);
        } else {
            // 字符不匹配，且下一个字符是 *，则忽略当前模式字符和 *
            return matchCore($str, $pattern, $strIdx, $patternIdx + 2);
        }
    }
    // 下一个字符不是 *，字符匹配，则字符串字符和模式字符都向后移动一个
    if ($pChar == $sChar || ($pChar == '.' && !empty($sChar))) {
        return matchCore($str, $pattern, $strIdx + 1, $patternIdx + 1);
    }

    return false;
}

$a = 'aaa';
$b = 'ab*.ba';
var_dump(match($a, $b));