leetcode 10. 正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
-
'.'匹配任意单个字符 -
'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。
示例 2:
输入：s = "aa", p = "a*" 输出：true 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：
输入：s = "ab", p = ".*" 输出：true 解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
提示：
-
1 <= s.length <= 20 -
1 <= p.length <= 30 -
s只包含从a-z的小写字母。 -
p只包含从a-z的小写字母，以及字符.和*。 -
保证每次出现字符
*时，前面都匹配到有效的字符
Related Topics
递归
字符串
动态规划
思路1：动态规划
参考leetcode官方解释。s是主串，p是正则匹配串。
dp[i][j]表示s中前i个字符和p中前j个字符的匹配结果。（因为有*这个正则表达，所以需要每一个都匹配）。
匹配的字符总共有3种形式：
-
p[j]是字符，直接判断
s[i] == p[j]，如果成立，那么-
dp[i][j] = dp[i-1][j-1]
-
-
p[j]是
.，那么s[i] ==p[j]直接成立，-
dp[i][j] = dp[i-1][j-1]
-
-
p[j]是
*，因为可能会出现多个零个或者多个p[j-1]。所以这个地方需要分析。(需要注意：dp[i] [j]的含义就是s中前i个字符和p中前j个字符匹配。)-
匹配零次的情况：
-
当s[i]!=p[j-1]时，可以把
p[j-1]*忽略掉,只要s中前i个字符和p中前j-2个字符匹配成功，那么p[j-1]p[j]也就是p[j-1]*当做0次出现。举例：s=aaa,p=aaab* 匹配-
dp[i][j] = dp[i][j-2]
-
-
当s[i]==p[j-1]时，有可能s的前i个字符已经和p中前j-1个字符匹配，那么最后的p[j-1]*就是多余的。举例：
s = aaa，b=aaaa*-
dp[i][j] = dp[i][j-2]
-
-
只要s中前i个字符和p中前j-2个字符匹配成功，那么P[j-1]*就是多余的，出现0次。
-
-
当出现多次的情况：
-
当s[i]==p[j-1]时，
p[j-1]*至少出现一次以上，那么可以把s[i]忽略掉，继续向前判断s中前i-1个字符和p中前j个字符。-
dp[i][j] = dp[i-1][j]
-
-
经过以上分析，
-
无论
s[i]和P[j-1]是否相等，都可能出现0次的情况。dp[i][j] = dp[i][j-2]
-
当s[i]==p[j-1]时，还可能出现匹配多次的情况。
dp[i][j] = dp[i-1][j] -
无论哪一种情况出现，dp[i] [j]就为true。
-
边界分析：
举例：s = aa, p=a*，
-
s[1]=p[1],那么dp[1][1]=true -
p[2]=*,那么s[1]=p[1] = dp[1][2] = dp[1][0] || dp[0][2] -
经过发现，我们还需要计算当s或者p为空串的情况。
-
当s为空，p不为空，可能出现true的情况。举例：s=“”，p=a* 答案为true
-
当s不为空，p为空，全部为false。
-
当s为空，p为空，直接为true。
-
所以需要特别计算当i=0的时候的dp[i] [j]。
-
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0] = true;
for(int i = 0 ; i <= m;i++){
for(int j = 1 ; j <= n;j++){
//如果第j个字符是*
if(p.charAt(j-1)=='*'){
//无论s第i个字符和p的第j-1个字符是否匹配成功，都可能出现0次情况
dp[i][j] = dp[i][j-2];
//如果s第i个字符和p的第j-1个字符匹配成功，可能出现多次情况(需要注意的是，第j-1个字符在s中的下标是i-2,这也是为什么在match中减一的原因)
if(match(s,p,i,j-1)){
dp[i][j] = dp[i][j] || dp[i-1][j];
}
}else if(match(s,p,i,j)){
dp[i][j] = dp[i-1][j-1];
}
}
}
return dp[m][n];
}
//p[j]不是*的情况下 匹配s第i个和p中第j个 第i个字符的下标是i-1
public boolean match(String s,String p,int i,int j){
//因为p[j]！=* 当s为空串，p不为空串，一定为false
if(i == 0){
return false;
}
//任意匹配 直接成功
if(p.charAt(j-1)=='.'){
return true;
}
return s.charAt(i-1)==p.charAt(j-1);
}
}
解答成功:
执行耗时:2 ms,击败了68.96% 的Java用户
内存消耗:39.7 MB,击败了31.39% 的Java用户
思路2：调用官方api
public boolean isMatch(String s, String p) {
return s.matches(p);
}
解答成功:
执行耗时:32 ms,击败了12.34% 的Java用户
内存消耗:41.5 MB,击败了5.02% 的Java用户
调用官方api可能会匹配其他正则，时间消耗有点大。