27 Feb 2024•PHP•Hard

Regular Expression Matching

match string against pattern with . and * using dynamic programming with memoization.

dp[i][j] = true if s[0..i] matches p[0..j]. handle three cases: exact match, . matches any, * matches zero or more of preceding character.

for *, try both zero matches (skip pattern) and one or more matches (consume string if character matches). use memoization to avoid recomputation.

cases

exact match: s[i] == p[j]
dot: p[j] == '.' matches any character
star: p[j] == '*' matches zero or more of p[j-1]

complexity

O(mn) time where m and n are string and pattern lengths. O(mn) space for dp table.

Solution files

PHP•regular-expression-matching/solution.php

class Solution {

function isMatch($s, $p) {
    $memo = [];
    return $this->helper($s, $p, class="syntax-number">0, class="syntax-number">0, $memo);    
}

function helper($s, $p, $i, $j, &$memo) {
    if (isset($memo[$i][$j])) {
        return $memo[$i][$j];
    }

    if ($j >= strlen($p)) {
        return $memo [$i][$j] = ($i >= strlen($s));
    }

    $match = ($i < strlen($s) && ($s[$i] == $p[$j] || $p[$j] == class="syntax-string">'.'));

    if ($j + class="syntax-number">1 < strlen($p) && $p[$j +class="syntax-number">1] == class="syntax-string">'*') {
        $memo[$i][$j] = $this->helper($s, $p, $i, $j +class="syntax-number">2, $memo) || ($match && $this->helper($s, $p, $i + class="syntax-number">1, $j, $memo));            
    } else {
        $memo[$i][$j] = $match && $this->helper($s, $p, $i + class="syntax-number">1, $j + class="syntax-number">1, $memo);
    }

return $memo[$i][$j];
}
}