剑指offer 面试题19 正则表达式匹配

最近正好在学编译原理,和计算理论,正则表达式接触的也比较多.

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

其实是一个较为简单的正则表达式,简单来说正则表达式就是一种模式,用来表示各种符合相应特性的字符串,题目中只有两种特殊情况

'.' 表示任意字符
'*'表示闭包,代表前一个字符可以取0或无数次

难点就在于这个* 有可能是一次,有可能0次,也有可能是多次,所以整个题目终点都在处理*符号.

一开始很容易就对两个字符串
1.s代表输入字符串
2.p代表模式字符串
使用两个指针依次匹配是否相等,或者等于'.'
在遇到'*'的再进行特殊的处理,

但写着写着发现'*'在不同的位置需要判断的情况过于复杂,没有办法一个一个判断很好的覆盖所有的情况,所以没有规划的判断会导致代码越来越混乱,太多的ifelse到最后我也没有调出正确结果.

于是借鉴了题解提供的动态规划的思路:

我们首先要构建一个二维数组,boolean dp[n+1][m+1]
其中n是s字符串的长度,m是p字符串的长度
而dp[i][j]所代表的含义是,s的前i个字符与p前j个字符的模式是否能够匹配
具体一点来说是s的[0,i) 和p的[0,j) 是否匹配,不包含第i和j.

动态规划就像是归纳假设一样最重要的两步
1.确定初始状态
首先,考虑字符串为null的情况,当s或者p为null的时候,我们直接认为是不匹配的

if(s==null||p==null){
            return false;
        }

其次,若s和p长度为0或者说为空的时候,我们认为

  dp[0][0] =true ;

2.确定递推关系
我们无需关心具体哪一个位置,递推关系只要关注该结果是如何通过上一步推导的
我们关心dp[i][j] 则需要根据s.charAt(i-1) p.charAt(j-1)的关系来进行判断,这也就是题目匹配的最主要的逻辑部分.我们分类讨论各种情况
(此处i-1 j-1仍是因为dp[i][j]的定义是左闭右开的原因)

根据题目,字符有a-z '.' '*' 三种
1)当s.charAt(i-1)==p.charAt(j-1)
也就是当前所在的位置的两个字符相等,可以认为
dp[i][j]=dp[i-1][j-1]

如果两个字符不相等的话,又有以下情况
2)当p.charAt(j-1)=='.'
由于'.'匹配任意字符,这个情况与情况1并没有区别
dp[i][j]=dp[i-1][j-1]

3)当p.charAt(j-1)==''
根据题目我们知道一定和它前面一个字符有关,并且他可能代表0个,1个或者多个,

i) 0个由于当前的字符与前的字符不匹配,所以我们可以忽略这个以及前字符.
例如当s=ab p=acb 的时候, 此时并不需要匹配c,则把c*视为0个.
这种情况下, 即p.charAt(j-2)!=s.charAt(i-1)
则我们让
dp[i][j] = dp[i][j-2] (相当于去掉p[j-1]和p[j-2])

ii)1个由于当前的字符与前的字符匹配且仅需要一个, 我们可以忽略掉号,仅仅做正常的字符匹配就行了即,p.charAt(j-2)==s.charAt(i-1)
例如 s=ab p=ab*
则dp[i][j]=dp[i][j-1]

iii)多个由于当前的字符与前的字符匹配且仅需要多个,
即p.charAt(j-2)==s.charAt(i-1) 且至少p.charAt(j-2)==s.charAt(i-2)
则dp[i][j] = dp[i-1][j] 这代表着如果i-1的串模式是匹配的,那么在输入一个相同的字符,将不影响这个结果.
例如s=abbb p=ab
具体来说abbb是否匹配ab* 相当于abb是否匹配ab* 相当于ab是否匹配ab*此时由前面1个的情况则又取决于ab(s)与ab(p)是否匹配.显然是成立的

最后
s.charAt(i-1)!=p.charAt(j-1) 且p.charAt(j-1)也不是'.'或者'*'的时候,
则代表模式无法匹配.dp[i][j]=false

结构图

代码示例:

public boolean isMatch(String s, String p) {
       \\判断是否为null
        if(s==null||p==null){
            return false;
        }
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0]=true;\\认为两个空串匹配
        for(int j=2;j<m+1;j++)
        {
            if(p.charAt(j-1)=='*'&&dp[0][j-2]) {
                dp[0][j] = true;
            }
        }
      
        for(int i = 1;i<n+1;i++){
            for(int j = 1;j<m+1;j++){
                char a= s.charAt(i-1);\\当前s的字符
                char b= p.charAt(j-1);\\当前p的字符
                if(a==b){ 
                    dp[i][j]=dp[i-1][j-1];
                }
                else{
                    if(b=='.'){
                        dp[i][j]=dp[i-1][j-1];
                    }
                    else if(b=='*'){
                        if(j>=2){ \\为了保证j-2不会出错,实际上*不可能前面没有字符
                            char c = p.charAt(j-2);
                            if(c==a||c=='.') { \\字符匹配与.号匹配情况相同,合并在一起
                                dp[i][j] = dp[i - 1][j] || dp[i][j - 1]; \\只有 p.charAt(j-2)==s.chatAt(i-1)或 p.charAt(j-2)==‘.’才可以让*取1个或者多个字符：
                            }
                            dp[i][j] = dp[i][j]||dp[i][j-2];\\上述的结果或*代表0个的情况
                        }

                    }
                    else{
                        dp[i][j]=false;
                    }
                }
            }
        }
        return dp[n][m];
    }