Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Constraints:
1 <= s.length <= 20
1 <= p.length <= 20
s contains only lowercase English letters.
p contains only lowercase English letters, '.', and '*'.
It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.
Solutions
Solution 1: Memoization Search
We design a function $dfs(i, j)$, which indicates whether the $i$-th character of $s$ matches the $j$-th character of $p$. The answer is $dfs(0, 0)$.
The calculation process of the function $dfs(i, j)$ is as follows:
If $j$ has reached the end of $p$, then if $i$ has also reached the end of $s$, the match is successful, otherwise, the match fails.
If the next character of $j$ is '*', we can choose to match $0$ $s[i]$ characters, which is $dfs(i, j + 2)$. If $i \lt m$ and $s[i]$ matches $p[j]$, we can choose to match $1$ $s[i]$ character, which is $dfs(i + 1, j)$.
If the next character of $j$ is not '*', then if $i \lt m$ and $s[i]$ matches $p[j]$, it is $dfs(i + 1, j + 1)$. Otherwise, the match fails.
During the process, we can use memoization search to avoid repeated calculations.
The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Here, $m$ and $n$ are the lengths of $s$ and $p$ respectively.
implSolution{#[allow(dead_code)]pubfnis_match(s:String,p:String)->bool{letn=s.len();letm=p.len();lets=s.chars().collect::<Vec<char>>();letp=p.chars().collect::<Vec<char>>();letmutdp=vec![vec![false;m+1];n+1];// Initialize the dp vectordp[0][0]=true;foriin1..=m{ifp[i-1]=='*'{dp[0][i]=dp[0][i-2];}}// Begin the actual dp processforiin1..=n{forjin1..=m{ifs[i-1]==p[j-1]||p[j-1]=='.'{dp[i][j]=dp[i-1][j-1];}ifp[j-1]=='*'{ifj>=2&&(s[i-1]==p[j-2]||p[j-2]=='.'){dp[i][j]=dp[i-1][j]||dp[i][j-2];}elseifj>=2&&s[i-1]!=p[j-2]{dp[i][j]=dp[i][j-2];}}}}dp[n][m]}}
We can convert the memoization search in Solution 1 into dynamic programming.
Define $f[i][j]$ to represent whether the first $i$ characters of string $s$ match the first $j$ characters of string $p$. The answer is $f[m][n]$. Initialize $f[0][0] = true$, indicating that the empty string and the empty regular expression match.
Similar to Solution 1, we can discuss different cases.
If $p[j - 1]$ is '*', we can choose to match $0$ $s[i - 1]$ characters, which is $f[i][j] = f[i][j - 2]$. If $s[i - 1]$ matches $p[j - 2]$, we can choose to match $1$ $s[i - 1]$ character, which is $f[i][j] = f[i][j] \lor f[i - 1][j]$.
If $p[j - 1]$ is not '*', then if $s[i - 1]$ matches $p[j - 1]$, it is $f[i][j] = f[i - 1][j - 1]$. Otherwise, the match fails.
The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Here, $m$ and $n$ are the lengths of $s$ and $p$ respectively.