10.正则表达式匹配

简介: 10.正则表达式匹配

字符串匹配

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.''*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

自己拿到这道题的第一感觉,是对字符规律p进行分析。p应该有3种元素,字母'a-z',.匹配任意字符,*匹配0个或多个前面的元素。可见*是配合前面的元素使用的,那么又可以分为两类,


1:字母或. 。.也可以看成一种字母,故将他们统称为字母。


2:* 辅助元素


于是我们对p进行匹配两种模式: 字母; 字母*。但是对字母* 进行匹配时会出现问题,无法确定匹配字母的个数。


官方解法提供了解决这种任意性的方法:动态规划


为了方便,我们用 f[i][j] 表示 s的前 i 个字符与 p 中的前 j 个字母是否能够匹配。考虑p的第j个字母的匹配情况:


如果p[j] 是字母,那么我们必须在s中匹配到相同的字母,即:

 

如果p[j] 是*,那么我们可以对 p[j-1] 进行任意次匹配。

匹配0次时:f[i][j] = f[i][j-2]

匹配1次时: f[i][j] = f[i-1][j-2], if s[i] = p[j-1]

匹配2次:f[i][j] = f[i-2][j-2], if s[i] = s[i-1] = p [j-1]

...

这样需要考虑很多种情况,但实际上字母* 匹配过程只会遇到两种情况:

1.匹配s末尾字符s[i],于是将s[i]去掉,继续匹配 ( f[i-1][j] )

2.不匹配字符p[j-1],丢掉p[j-1]+p[j]。( f[i][j-2] )

于是有:

 

综上:状态转移方程f[i][j] 为:

matches是判断字符匹配的辅助函数。

边界条件 f[0][0] = true ,即空字符串可以匹配。

 

public class Q10 {
    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) == '*') { //字符串是从0开始的,所以第j个字符下标为j-1
                    if (matches(s,p,i,j-1)) {
                        f[i][j] = f[i][j-2] || f[i-1][j];
                    }
                    else {
                        f[i][j] = f[i][j-2];
                    }
                }
                else {
                    if (matches(s,p,i,j)) {
                        f[i][j] = f[i-1][j-1];
                    }
                }
            }
 
        }
        return f[m][n];
 
    }
 
    //辅助函数,判断s[i]和p[j]是否匹配
    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);
    }
}
相关文章
|
5月前
|
索引 Python
正则表达式详解
正则表达式详解
|
6月前
|
编译器 Python
正则表达式
正则表达式
30 0
|
6月前
最全面的常用正则表达式大全
最全面的常用正则表达式大全
常用正则表达式
常用正则表达式
68 0
|
6月前
正则表达式的使用
正则表达式的使用
47 1
|
JavaScript 前端开发 Java
正则表达式(全)
正则表达式是由一些具有特殊含义的字符组成的字符串,多用于查找、替换符合规则的字符串。在表单验证、Url映射等处都会经常用到。
227 0
【正则表达式】总结
【正则表达式】总结
100 0
正则表达式引例
正则表达式引例
144 0
第177天:常用正则表达式(最全)
常用正则表达式 1 2 /* 常用正则表达式大全!(例如:匹配中文、匹配html) 3 4 匹配中文字符的正则表达式: [u4e00-u9fa5] 5 评注:匹配中文还真是个头疼的事,有了这个表达式就好办了 6 匹配双字节字符(包括汉字在内):[^x0...
1122 0