剑指Offer52:正则表达式匹配(Java)

luofuIT成长记录 2020-02-25

参考:
左程云进阶算法第8节视频内容(2小时18分钟处) 视频百度网盘:链接:https://pan.baidu.com/s/1beVfli8bmH9obwNW3NT3Kg 提取码:q5bi
loveforever个人博客网站:https://zhenganwen.top/posts/310d4836/ (有左神算法基础,进阶视频完整笔记代码)

思路分析:

递归版本大概听懂了,动态规划的解法听不懂。看不懂这个题的网上解析的博客不妨看看左神的视频。
递归解法有两个关键点:

  1. 递归解法以函数f(i,j)为基础,str的i,及其后面位置的字符能否和exp的j,及其后面位置上的字符一一匹配,能返回true,不能返回false.然后递归调用本身,判断i+1,j+1的情况。
  2. 因为*很特殊,判断str[i]和exp[j]是否匹配根据*分三种情况:(1).j==exp.length(j,j+1位置都没有字符)。(2).j+1位置有字符但不是*或j有子符j+1没有字符。(3).j+1位置有子符是*。

题目描述

请实现一个函数用来匹配包括‘.‘和‘‘的正则表达式。模式中的字符‘.‘表示任意一个字符,而‘‘表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"abaca"匹配,但是与"aa.a"和"ab*a"均不匹配

java代码:

public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        return match(str,pattern,0,0);
    }
    
     //这是暴力递归方法
    //这个函数只判断str的i及其之后,与exp的j及其之后是否一一匹配,i,j之前的不管。
    public static boolean match(char[]str,char[]exp,int i,int j){
        //若j没有了字符,则i必须没有字符,否则返回false;
        if(j==exp.length){
            return i==str.length;
        }
        //隐含条件:exp[j]一定是有字符的
        //在j是exp的最后一个字符,或者j后面的字符不是'*'的条件下。exp[j]必须与str[i]匹配,否则返回false
        if(j+1==exp.length||exp[j+1]!='*'){
            return i!=str.length&&(exp[j]==str[i]||exp[j]=='.')&&match(str,exp,i+1,j+1);
        }
        //隐含条件:j后面一定有字符且是'*'
        //在str[i]一定有字符,且str[i]与exp[j]匹配的情况下,通过改变i值判断多种情况是否能够匹配。
        while(i!=str.length&&(exp[j]==str[i]||exp[j]=='.')){
            if(match(str,exp,i,j+2)){
                return true;//只要while循环中有一个匹配成功,即这次的i,j匹配成功
            }
            i++;//通过改变i值,判断了以下情况是否能够匹配:exp[j]匹配了0个str[i],1个str[i],多个str[i]
        }
        return match(str,exp,i,j+2);
    }
}

这个while循环不好理解,loveforever个人博客网站的这个图可以帮助理解
剑指Offer52:正则表达式匹配(Java)

相关推荐