文章目录
-
-
- 题目描述
- Java解决方法
-
题目描述
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5CN4E2NxgTO3UzY5czNiNmYxQ2NycjYidzN2MTM4MDNw8CX0JXZ252bj91Ztl2Lc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
Java解决方法
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] f = new boolean[m + 1][n + 1];
f[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p.charAt(j - 1) == '*') {
f[i][j] = f[i][j - 2];
if (matches(s, p, i, j - 1)) {
f[i][j] = f[i][j] || f[i - 1][j];
}
} else {
if (matches(s, p, i, j)) {
f[i][j] = f[i - 1][j - 1];
}
}
}
}
return f[m][n];
}
public boolean matches(String s, String p, int i, int j) {
if (i == 0) {
return false;
}
if (p.charAt(j - 1) == '.') {
return true;
}
return s.charAt(i - 1) == p.charAt(j - 1);
}
}
由于改题的解决方法参照官方给的答案,所以不放运行情况。但是该题动态规划的思想实在是非常好。
我们用 f[i][j] 表示 s的前 i 个字符与 p 中的前 j个字符是否能够匹配。
![]()
leetcode刷题_正则表达式匹配