给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。 '.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。 java实现
时间: 2023-03-04 15:33:15 浏览: 44
以下是Java中实现支持'.'和'*'的正则表达式匹配的示例代码:
```java
public boolean isMatch(String s, String p) {
// dp[i][j]表示s的前i个字符与p的前j个字符是否匹配
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true; // 空字符串匹配空字符串
for (int i = 0; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 2] || (i > 0 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') && dp[i - 1][j]);
} else {
dp[i][j] = i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') && dp[i - 1][j - 1];
}
}
}
return dp[s.length()][p.length()];
}
```
上述代码中,我们使用动态规划的思想,通过填充dp数组来解决问题。我们定义dp[i][j]表示s的前i个字符与p的前j个字符是否匹配。首先,当两个字符串都为空时,它们是匹配的,因此dp[0][0]为true。接下来,我们需要分别考虑p的第j个字符是'.'、'*'或其他情况。
1. 如果p的第j个字符是'.',那么它可以匹配s的任意单个字符。因此,只需要判断s的前i-1个字符与p的前j-1个字符是否匹配,即dp[i-1][j-1]。
2. 如果p的第j个字符是'*',那么它可以匹配零个或多个前面的那一个字符。我们需要考虑两种情况:
- 零个匹配:这时候需要忽略p中的'*'和它前面的字符,因此只需要判断s的前i个字符与p的前j-2个字符是否匹配,即dp[i][j-2]。
- 多个匹配:这时候需要判断s的第i个字符是否能够和p中'*'前面的字符匹配,如果能够匹配,那么s的前i个字符就可以匹配p的前j个字符。因此,只需要判断s的前i-1个字符与p的前j个字符是否匹配,即dp[i-1][j],并且需要保证s的第i个字符和p中'*'前面的字符匹配,即s.charAt(i-1) == p.charAt(j-2)或者p.charAt(j-2) == '.'。
3. 如果p的第j个字符既不是'.'也不是'*',那么只有在s