题解 | #正则表达式匹配#
正则表达式匹配
https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4
二刷,第二次理解了
希望我下次再刷,不会又不懂了
其他的不说了,就说*的匹配:
1,*匹配为0, 那就是匹配模式前两位的模式dp[i][j-2]
2,*不匹配为0,又分为以下情况:
i、*的前导字符等于当前字符串字符(条件:pattern.charAt(j - 2) == str.charAt(i - 1)),并且只与当前字符匹配(匹配一次),所以转移*前一个字符与当前字符串字符的匹配状态:dp[i][j-1]
ii、*的前导字符等于当前字符串字符(条件:pattern.charAt(j - 2) == str.charAt(i - 1)),并且是匹配多次匹配到当前字符串字符的,意味着当前字符串字符的前一个字符也与这个*匹配。因此又有条件:i>=2&&str.charAt(i - 2) == str.charAt(i - 1)时,可以转移前一个字符串字符与*的匹配状态:dp[i-1][j]
iii、*的前导字符为.(条件:pattern.charAt(j - 2) == '.'),同样对照上述两种情况,匹配一次和匹配多次,不同的是,如果是.的话,匹配多次就不需要字符串的上一个字符与当前字符相同,都可以被.的*匹配到,因此可以直接转移上述两种状态:dp[i-1][j]||dp[i][j-1]
3,其他情况均无法匹配
上述2的三种逻辑的代码如下:
if (pattern.charAt(j - 2) == str.charAt(i - 1)) { dp[i][j] |= dp[i][j - 1]; if(i>=2&&str.charAt(i - 2) == str.charAt(i - 1))dp[i][j] |=dp[i-1][j]; }else if( pattern.charAt(j - 2) == '.') dp[i][j] |= (dp[i][j - 1]||dp[i-1][j]);
最后上述所有判断是同级别的,即一种状态为true,当前状态就true,所以程序上依次进行或操作即可。但是需要保证j>=2。
以下是完整代码:
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str string字符串 * @param pattern string字符串 * @return bool布尔型 */ public boolean match (String str, String pattern) { // write code here //1、创建状态转移数组,第i个字符与第j个模式是否匹配 int l1=str.length(); int l2=pattern.length(); boolean[][] dp = new boolean[l1+1][l2+1]; //2、初始化边界 dp[0][0]=true; for(int i=1;i<=l1;i++)dp[i][0]=false; for(int j=1;j<=l2;j++){ if(pattern.charAt(j-1)=='*'&&j-2>=0)dp[0][j]=dp[0][j-2]; else dp[0][j]=false; } //3、状态转移方程 for(int i=1;i<=l1;i++){ for(int j=1;j<=l2;j++){ if(str.charAt(i-1)==pattern.charAt(j-1)||(pattern.charAt(j-1)=='.'))dp[i][j]=dp[i-1][j-1]; else if(pattern.charAt(j-1)=='*'){ if (j >= 2) { dp[i][j] |= dp[i][j - 2]; if (pattern.charAt(j - 2) == str.charAt(i - 1)){ dp[i][j] |= dp[i][j - 1]; if(i>=2&&str.charAt(i - 2) == str.charAt(i - 1))dp[i][j] |=dp[i-1][j]; }else if( pattern.charAt(j - 2) == '.')dp[i][j] |= (dp[i][j - 1]||dp[i-1][j]); } }else dp[i][j]=false; } } //4、匹配到最后一个字符和最后一个模式可以匹配即可以匹配 return dp[l1][l2]; } }