10-正则表达式

10. 正则表达式匹配

定义状态

  • 定义动态数组dp[m][n] (n为字符串p的长度+1,m为字符串s的长度+1)
    • 为什么要加1
    • 因为我们还要处理空字符串的情况,比如p为空,s为空,或者p为空,s不为空
  • dp[m][n] 的含义:p的前n1 个字符能否匹配s的前m1个字符
    • 为什么是n-1和m-1?
    • 因为动态数组里面加了一列和一行空字符的匹配情况,故需要-1才能对应相应字符串

因此创建好的dp数组如下图:

确定动态转移方程

说明:为了区别dp数组与字符串索引的区别(因为相差1),我们设 i=r1,j=c1 (r为dp里面的行索引,c为dp里面的列索引)

有以下几种情况是需要我们处理的:

  • s[i]=p[j] || p[j]==. (即正好能够匹配或者相对应的是一个 .

那么我们只需要看一下前面 dp[r1][c1]的状态,dp[r][c]继续延续即可

即状态转移方程为 dp[r][c]=dp[r1][c1]

  • 当 $p[j] ==’$)

    两种情况分别对应的处理方式为:

    如果 的前一个字符正好对应了s,状态转移过程为:dp[r][c]=dp[r1][c]

    如果是的前一个字符为 . 那么只需看.的前面字符匹配情况,状态转移过程为: dp[r][c]=dp[r][c2]

边界:

  • 首先我们要确定 dp[0][0],当p为空,s为空时,肯定匹配成功。那么dp[0][0]=true

  • 当 p 为空字符串,而s不为空时,dp数组必定为False,正好初始化dp数组的时候设置的是False;即dp数组的第一列为False可以确定

  • 当s为空字符串,而p不为空时,我们无需判断p里面的第一个值是否为””,如果为””,那肯定匹配不到为Fasle,原数组正好是Fasle,所以直接从2开始判断即可。如果遇到了*,只要判断其对应的前面两个元素的dp值

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public boolean isMatch(String s, String p) {
int n = s.length();
int m = p.length();
boolean[][] dp=new boolean[n+1][m+1];
s = ' '+s;
p = ' '+p;
dp[0][0] = true;

for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i==0 && j==0) continue;
if(p.charAt(j) != '*'){
if(p.charAt(j)=='.' || s.charAt(i)==p.charAt(j)){
if(i>0 && j>0){
dp[i][j] = dp[i-1][j-1];
}
}
} else{
if(j>=2) dp[i][j] = dp[i][j-2];
if(i>0 && j>0){
if(p.charAt(j-1) == '.' || s.charAt(i)==p.charAt(j-1)){
if(dp[i-1][j]) dp[i][j]=true;
}
}
}
}
}
return dp[n][m];
}

}