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

题意整理

• 用模式串来检验整个匹配串。
• 模式串中的'.'匹配任何字符，'*'表示它前面的字符可以出现任意次（即0到无穷次）。

方法一（记忆化递归）

1.解题思路

1. 递归终止条件：当模式串走完的时候，递归终止，如果此时，原串也走完了，则匹配成功；如果没走完，则匹配失败。
2. 每一层递归从上一层获取什么：当模式串p的当前字符的后一个为'*'时，我们将'*'所在位置和前一个位置连在一起考虑，不管是否满足原串与模式串匹配，都可以匹配0个字符，即s的游标不动，p的游标往后移2格；如果满足原串与模式串匹配，则匹配0个或大于0的任意个字符，只需s的游标后移1格，p的游标不动。当模式串p的当前字符后一个不为'*'时，只需看原串与模式串是否匹配，若匹配，一起往后走一个格子；若不匹配，返回false。
3. 每一层递归返回什么：根据实际的情况，将原串s和模式串p后移若干格子。

由于直接递归会走很多弯路，我们可以用一个记忆数组来存储递归过程中，已经确定过的情况，然后进行剪枝，如果发现记忆化数组中存储了已经出现过的情况，直接返回。

2.代码实现

普通递归:

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {

        return match(str.toCharArray(),0,pattern.toCharArray(),0);
    }

    private boolean match(char[] s,int si,char[] p,int pi){
        ////如果模式串走完了，原串没走完，则返回false；走完了，则返回true
        if(pi>=p.length) return si>=s.length;

        if(pi+1<p.length&&p[pi+1]=='*'){
             //如果满足'*'前一个字符与原串匹配
            if(si<s.length&&(s[si]==p[pi]||p[pi]=='.')){
                 //<*和前一个字符>匹配<原串字符>1到无穷次或者0次
                return match(s,si+1,p,pi)
                     ||match(s,si,p,pi+2);
            }
            //<*和前一个字符>匹配<原串字符>0次
            return match(s,si,p,pi+2);


        }

        //<模式串字符>匹配<原串字符>1次
        if(si<s.length&&(s[si]==p[pi]||p[pi]=='.')){
            return match(s,si+1,p,pi+1);
        }

        return false;
    }
}

记忆化递归：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    int[][] memo;

    public boolean match (String str, String pattern) {
        //初始化记忆数组
        memo=new int[str.length()+1][pattern.length()+1];

        return match(str.toCharArray(),0,pattern.toCharArray(),0);
    }

    private boolean match(char[] s,int si,char[] p,int pi){
        //如果模式串走完了，原串没走完，则返回false；走完了，则返回true
        if(pi>=p.length) return si>=s.length;

        //如果之前某种情况被memo记录下来，并且是对的，则返回true
        if(memo[si][pi]!=0) return memo[si][pi]==1;

        if(pi+1<p.length&&p[pi+1]=='*'){
            //如果满足'*'前一个字符与原串匹配
            if(si<s.length&&(s[si]==p[pi]||p[pi]=='.')){
                //<*和前一个字符>匹配<原串字符>1到无穷次或者0次
                boolean f=match(s,si+1,p,pi)
                        ||match(s,si,p,pi+2);
                memo[si][pi]=f?1:-1;
                return f;
            }
            //<*和前一个字符>匹配<原串字符>0次
            boolean f=match(s,si,p,pi+2);
            memo[si][pi]=f?1:-1;
            return f;
        }

        //<模式串字符>匹配<原串字符>1次
        if(si<s.length&&(s[si]==p[pi]||p[pi]=='.')){
            boolean f=match(s,si+1,p,pi+1);
            memo[si][pi]=f?1:-1;
            return f;
        }

        return false;
    }
}

3.复杂度分析

• 时间复杂度：最坏的情况，会遍历整个记忆数组，所以时间复杂度为 。
• 空间复杂度：需要额外 大小的记忆数组，所以空间复杂度为。

方法二（动态规划）

1.解题思路

• 状态定义： 表示原字符串长度为n，模式串长度为m时，是否能够匹配。
• 初始化：当原串和模式串都为空时，显然能够匹配， ;当模式串为空，而原串不为空时，均为 。
• 状态转移：分模式串后一个位置是否为'*'进行讨论,为'*'时，将'*'与前一个位置合并起来进行考虑。如果后一个位置不为'*'，并且当前模式串字符和原串字符匹配，则满足 ；如果后一个位置为'*'，
  无论是否匹配，均满足dp[i][j]=dp[i][j-2] (匹配0次)，如果匹配，满足 (匹配1到无穷次或0次)

动图展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */

    public boolean match (String str, String pattern) {
        int n=str.length();
        int m=pattern.length();
        boolean[][] dp=new boolean[n+1][m+1];

        //初始化
        dp[0][0]=true;
        for(int i=1;i<=n;i++){
            dp[i][0]=false;
        }

        //分模式串的后一个位置是否为*进行讨论,为*时，将*与前一个位置合并起来进行考虑
        for(int i=0;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(pattern.charAt(j-1)!='*'){
                    //当前模式串字符和原串字符匹配
                    if(i>0&&(str.charAt(i-1)==pattern.charAt(j-1)||(pattern.charAt(j-1)=='.'))){
                        dp[i][j]=dp[i-1][j-1];
                    }
                }
                else{
                    if(j>=2){
                        //不管是否匹配，都可以将当前字符绑定上*匹配原串字符0次
                        dp[i][j]=dp[i][j-2];
                        //当前模式串字符和原串字符匹配
                        if(i>0&&(str.charAt(i-1)==pattern.charAt(j-2)||(pattern.charAt(j-2)=='.'))){
                            dp[i][j]=dp[i-1][j]||dp[i][j-2];
                        }
                    }
                }
            }
        }
        return dp[n][m];
    }


}

3.复杂度分析

• 时间复杂度：需要计算所有的状态，总共有 种状态，所以时间复杂度为 。
• 空间复杂度：需要额外大小的dp数组，所以空间复杂度为 。