来源Leetcode第10题正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持’.’和’*‘的正则表达式匹配。
‘.’匹配任意单个字符
‘*‘匹配零个或多个前面的那一个元素
所谓匹配，是要 涵盖整个字符串s的，而 不是部分字符串s 。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ‘.’和’*‘。
示例 4:
输入:
s = “aab”
p = “c*a*b”
输出: true
解释: 因为’*‘表示零个或多个，这里’c’为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。
回溯
采用递归的思想，当前层匹配了就可以匹配下一层。当遇到字符’.’时可以认为直接匹配进入下一层，当遇到字符’*‘时要考虑字符’*‘前一个字符出现的次数是0次还是多次，所以在递归的时候有两个方向的递归，一个是认为前一个字符出现0次，所以直接从模式串p的第3个字符开始匹配，一个是认为出现多次，因而需要模式串第一个字符与匹配串第一个字符匹配，在来匹配匹配串后续字符。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public boolean isMatch(String text, String pattern) {
if (pattern.isEmpty()) return text.isEmpty();
boolean first_match = (!text.isEmpty() &&
(pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
if (pattern.length() >= 2 && pattern.charAt(1) == '*'){
return (isMatch(text, pattern.substring(2)) ||
(first_match && isMatch(text.substring(1), pattern)));
} else {
return first_match && isMatch(text.substring(1), pattern.substring(1));
}
}
}
|
动态规划
可以看到回溯的话时空复杂度相当的高，因为题目拥有最优子结构，一个自然的想法是将中间结果保存起来。我们通过用dp[i,j]表示text[i:]和pattern[j:]是否能匹配，即用户dp[i][j]表示s的前i个能否被p的前j的匹配。
考虑转移方程：
1.p[j] == s[i] -> dp[i][j] = dp[i-1][j-1]
2.if p[j] == ‘.‘ -> dp[i][j] = dp[i-1][j-1]
3.if p[j] = ‘*‘ ->
if p[j-1] != s[i] -> dp[i][j] = dp[i][j-2] //对应示例4，’*‘前的字符出现了0次
if p[j-1] == s[i] || p[j-1] == ‘.‘ -> dp[i][j] = dp[i-1][j] || dp[i][j] = dp[i][j-1] || dp[i][j] = dp[i][j-2] //分别对应着若干个字符匹配、单个字符匹配、没有字符匹配
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public boolean isMatch(String s, String p) {
int ls = s.length(), lp = p.length();
boolean[][] dp = new boolean[ls + 1][lp + 1];
dp[0][0] = true;
for(int j = 2; j <= lp; j++)
dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';
for(int i = 1; i <= ls; i++) {
for(int j = 1; j <= lp; j++) {
if(p.charAt(j-1) == '*')
dp[i][j] = dp[i][j - 2] || dp[i - 1][j] &&
(s.charAt(i-1) == p.charAt(j - 2) || p.charAt(j - 2) == '.');
else if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.')
dp[i][j] = dp[i - 1][j - 1];
}
}
return dp[ls][lp];
}
}
|