题解 | #正则表达式匹配#

正则表达式匹配

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

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-25 17:23
做完了怎么知道过没过呀
投递京东等公司10个岗位
点赞 评论 收藏
分享
06-02 15:17
门头沟学院 Java
心爱的idea:怎么会呢 应该是打招呼有问题 问就说实习6个月全国可飞随时到岗
点赞 评论 收藏
分享
07-25 10:31
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务