剑指offer-52、正则表达式匹配
<h2 id="题描述">题⽬描述</h2><p>请实现⼀个函数⽤来匹配包括' . '和' * '的正则表达式。模式中的字符' . '表示任意⼀个字符，<br>
⽽' * '表示它前⾯的字符可以出现任意次（包含0 次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串" aaa "与模式" a.a "和" ab*ac*a "匹配，但是与" aa.a "和" ab*a "均不匹<br>
配</p>
<p>示例1<br>
输⼊: "aaa","a*a"<br>
返回值: true</p>
<p>示例2<br>
输⼊："aad","c*a*d"<br>
返回值：true<br>
说明：因为这⾥ c 为 0 个，a被重复⼀次， * 表示零个或多个a。因此可以匹配字符串 "aad"。</p>
<p>示例3<br>
输⼊："",".*"<br>
返回值：true<br>
说明：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="递归">递归</h3>
<p>分类讨论，原串定义为str ,模式串为pattern 。`</p>
<ul>
<li>如果pattern ⻓度为0
<ul>
<li>且str ⻓度为0 ,说明刚刚好匹配完，返回ture</li>
<li>str ⻓度不为0 ，说明没有匹配完，返回false</li>
</ul>
</li>
<li>如果pattern 的⻓度⼤于0
<ul>
<li>如果pattern 的⻓度⼤于1 ，且第2 个字符是* ，说明前⾯的字符可以匹配0 ， 1 或者多次
<ul>
<li>分为两种情况讨论：⼀种是直接把* 和* 前⾯的字符去掉，相当于匹配了0 个，然后接着⽐较；另外⼀种是，如果str 的⻓度⼤于0 ，并且第⼀个字符匹配，那就把str 的第⼀个字符去掉，两者接着匹配。</li>
</ul>
</li>
<li>否则，说明第⼆个字符不是 * ，那么就直接⽐较第⼀个字符是不是匹配，同时将后⾯的字符进⾏匹配。</li>
</ul>
</li>
</ul>
<p>注意：上⾯说的第⼀个字符是不是匹配，除了两个字符相等的情况，其实还有模式串的字符为' . '的情况。</p>
<pre><code class="language-java">public class Solution {
public boolean isMatch(String s, String p) {
// 模式串为空时，文本串也必须为空才匹配
if (p.isEmpty()) return s.isEmpty();
// 检查首字符匹配：文本串非空且字符相等或模式为'.'
boolean firstMatch = !s.isEmpty() &&
(s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
// 处理'*'通配符（确保模式长度≥2且第二个字符是'*'）
if (p.length() >= 2 && p.charAt(1) == '*') {
// 两种情况：1) '*'匹配0个前驱字符 2) 匹配1个及以上前驱字符
return isMatch(s, p.substring(2)) ||
(firstMatch && isMatch(s.substring(1), p));
} else {
// 无'*'情况：首字符匹配且剩余部分也匹配
return firstMatch && isMatch(s.substring(1), p.substring(1));
}
}
}
</code></pre>
<ul>
<li>时间复杂度：最坏O((m+n)2^(m+n))</li>
<li>空间复杂度：O(m²+n²)递归栈</li>
</ul>
<h3 id="记忆化搜索递归缓存">记忆化搜索（递归+缓存）</h3>
<p>在递归基础上添加缓存，避免重复计算。使用二维数组存储s和p的匹配结果，避免重复递归</p>
<pre><code class="language-java">public class Solution {
private Boolean[][] memo; // 缓存数组：null未计算，true/false已计算
public boolean isMatch(String s, String p) {
memo = new Boolean;
return dfs(0, 0, s, p);
}
private boolean dfs(int i, int j, String s, String p) {
// 检查缓存是否存在当前子问题的解
if (memo != null) return memo;
boolean result;
// 模式串耗尽时，文本串也必须耗尽
if (j == p.length()) {
result = (i == s.length());
} else {
// 计算当前首字符匹配状态
boolean firstMatch = (i < s.length()) &&
(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
// 处理'*'通配符
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
result = dfs(i, j + 2, s, p) || // 匹配0次
(firstMatch && dfs(i + 1, j, s, p)); // 匹配1+次
} else {
result = firstMatch && dfs(i + 1, j + 1, s, p);
}
}
memo = result; // 存储结果到缓存
return result;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(m×n)</li>
<li>空间复杂度：O(m×n)</li>
</ul>
<h3 id="动态规划推荐">动态规划（推荐）</h3>
<p>动态规划：</p>
<ol>
<li>⾸先定义状态：⽤⼀个⼆维数组（套路） <code>dp</code> ⽤来表示str 的前i 个字符和pattern 的前j 个字符是否匹配。</li>
<li>初始化简单状态
<ul>
<li><code>dp= true</code> ,表示两个空的字符串是匹配的。</li>
<li>dp 数组的⾸列，除了<code>dp 为true</code> ，其他的都是false 。因为pattern 为空，但是s 不为空的时候，肯定不匹配。</li>
<li>dp 的⾸⾏，也就是str 为空的时候，如果pattern 的偶数位都是“*”,那么就可以匹配，因为可以选择匹配0 次。</li>
</ul>
</li>
<li>初始化前⾯之后，后⾯的从索引1 开始匹配：
<ol>
<li>pattern 的第j 个字符为“ * ”(即是 <code>pattern=='*'</code> )
<ol>
<li>如果<code>dp==true</code> ，那么<code>dp=true</code> (相当于str的前i和pattern的前j-2个字符匹配，此时的* 前⾯的那个字符出现了0 次)。</li>
<li>如果<code>dp==true</code> 且<code>str==pattern</code> ，则<code>dp =true</code> 。（如果str 的前i - 1 个字符和pattern 的前j 个字符匹配，并且str 的第i 个字符和pattern 的第j - 1 个字符相等,相当于‘ * ’前⾯的字符出现了1 次）</li>
<li>如果<code>dp=true</code> 且<code>pattern=='.'</code> 的时候，则<code>dp=true</code> 。(表示str 的前i-1 个和patten 的前j 个匹配，并且pattern 的第j-1 个是‘ . ’，第j 个是‘ * ’,那么说明可以匹配任何字符任何次数，⾃然str 可以多匹配⼀个字符。)</li>
</ol>
</li>
<li>pattern 的第j 个字符不为“ * ”(即是<code>pattern！='*'</code> )
<ol>
<li>如果<code>dp=true and str == pattern</code> 时，则<code>dp=true</code> 。（也就是前⾯匹配，接下来的字符⼀样匹配）</li>
<li>如果<code>dp=true</code> 且<code>pattern=='.'</code> ，那么<code>dp=true</code> 。(其实也是. 可以匹配任何字符)</li>
</ol>
</li>
</ol>
</li>
</ol>
<p>处理完数组之后，最后返回<code>dp</code> ，也就是str 的前n 个和pattern 的前m 个字符是否匹配。</p>
<pre><code class="language-java">public boolean match(String str, String pattern) {
if (pattern.length() == 0) {
return str.length() == 0;
}
int n = str.length() + 1;
int m = pattern.length() + 1;
boolean[][] dp = new boolean;
dp = true;
for (int j = 2; j < m; j = j + 2) {
if (dp && pattern.charAt(j - 1) == '*') {
dp = true;
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (pattern.charAt(j - 1) == '*') {
dp = dp || dp && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.');
} else {
dp = dp && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.');
}
}
}
return dp;
}
</code></pre>
<ul>
<li>时间复杂度 O(mn) ： 其中 m , n 分别为 str 和 pattern 的⻓度，状态转移需遍历整个 dp 矩阵。</li>
<li>空间复杂度 O(mn) ： 状态矩阵 dp 使⽤ O(mn) 的额外空间。</li>
</ul>
<h3 id="状态机优化空间优化dp">状态机优化（空间优化DP）</h3>
<p>状态机优化：滚动数组降低空间复杂度，只保留当前行和上一行的状态，空间优化到O(n)</p>
<pre><code class="language-java">public class Solution {
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[] dp = new boolean;
boolean[] prev = new boolean;
// 初始化第一行（空文本串情况）
dp = true;
for (int j = 2; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp = dp;
}
}
for (int i = 1; i <= m; i++) {
// 保存上一行状态
boolean[] temp = prev;
prev = dp;
dp = temp;
// 初始化当前行首列
dp = false;
for (int j = 1; j <= n; j++) {
char sc = s.charAt(i - 1);
char pc = p.charAt(j - 1);
if (pc == '*') {
char prevChar = p.charAt(j - 2);
boolean matchZero = dp;
boolean matchMulti = (prevChar == sc || prevChar == '.') && prev;
dp = matchZero || matchMulti;
} else {
dp = (pc == '.' || pc == sc) && prev;
}
}
}
return dp;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(m×n)</li>
<li>空间复杂度：O(n)</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19346982
頁:
[1]