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); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。