Leet Code 10.正则表达式匹配

给你一个字符串s和一个字符规律p，请你来实现一个支持 '.'和 '*'的正则表达式匹配

解决这个问题有两种方法：回溯和动态规划

回溯

字符串为s，正则表达式为p。

流程如下：

当p为NULL，s为NULL匹配成功，s不为NULL匹配失败。
s不为NULL，匹配s和p的第一个字符，注意 '.'。
判断p下一个字符是否为 '*'，也要判断p长度是否大于2，否则会报读取索引错误。
若是，匹配s和p.substring(2)或s.substring(1)&&first_match，这样才能回溯所有可能性。
若不是，如果第一个字符相同则匹配s.substring(1)和p.substring(1)。
不相同返回false。

import java.util.*;

public class leetcode {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.nextLine();
        String p = scan.nextLine();
        boolean match = isMatch(s,p);
        System.out.println(match);
    }

    public static boolean isMatch(String s, String p) {
        if(p.isEmpty() && s.isEmpty()) return true;
        if(p.isEmpty() && !s.isEmpty()) return false;
        //匹配第一个字符
        boolean first_match = !s.isEmpty() && ((s.charAt(0) == p.charAt(0)) || p.charAt(0) =='.');

        //判断p第二个字符是否为*
        if(p.length() >= 2 && p.charAt(1)=='*' ) {
            return isMatch(s,p.substring(2)) || first_match && isMatch(s.substring(1),p);
        }
        else {
            if(first_match==true){
                return isMatch(s.substring(1),p.substring(1));
            }
            else
                return false;
        }
    }
}

动态规划

动态规划分为自顶向下和自底向上两种形式。

这次采用自顶向下。其中dp[i][j]表示s前i个字符和p前j个字符能够匹配。

规则归纳：

如果s[i]==p[j]，则dp[i][j]=dp[i-1][j-1]
如果p[j]=='.'，则dp[i][j]=dp[i-1][j-1]
如果p[j]=='*'，则分两种情况：
第一种情况是p[j-1]!=s[i]，那么要去掉这个字符，dp[i][j]=dp[i][j-2]
第二种情况是p[j-1]==s[i]或者p[j-1]=='.'，那么可以一直匹配，这时的匹配情况又有三种。

dp[i][j]=dp[i-1][j]//匹配多个字符
dp[i][j]=dp[i][j-1]//匹配单个字符
dp[i][j]=dp[i][j-2]//匹配0个字符
三种情况，满足一种即可

初始化规则：

初始化第一行dp[0][j]
首先dp[0][0]=true,dp[0][1]=false
if(p[j-1]=='*') dp[0][j]=dp[0][j-2]

代码

import java.util.*;

public class leetcode {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.nextLine();
        String p = scan.nextLine();
        boolean match = isMatch(s,p);
        System.out.println(match);
    }

    public static boolean isMatch(String s, String p) {
        //p为null，s不为null则返回false，s为null返回true
        if(p.isEmpty()) return s.isEmpty();

        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0]=true;
        dp[0][1]=false;
        //初始化dp[0][0:p.length()]
        for(int j=2; j<p.length()+1 ;j++) {
            if(p.charAt(j-1)=='*')
                dp[0][j] = dp[0][j-2];
        }
        //遍历整个dp[][]完成动态规划过程
        for(int i=0; i<s.length(); i++) {
            for(int j=0; j<p.length(); j++) {
                //p[j]是否为*
                if(p.charAt(j)=='*') {
                    //两种情况，p[j-1]与s[i]是否相等
                    if(s.charAt(i)==p.charAt(j-1) || p.charAt(j-1)=='.') {
                        //相等的话有三种情况
                        dp[i+1][j+1]=dp[i][j+1] || dp[i+1][j] || dp[i+1][j-1] ;
                    }
                    else {
                        //p[j-1]!=s[i]，需要去掉p[j-1]和p[j]
                        dp[i+1][j+1] = dp[i+1][j-1];
                    }
                }
                else {
                    //p[j]不为*
                    if(s.charAt(i)==p.charAt(j) || p.charAt(j)=='.') {
                        dp[i+1][j+1]=dp[i][j];
                    }
                    else {
                        dp[i+1][j+1]=false;
                    }
                }

            }
        }
        return dp[s.length()][p.length()];
    }
}

小结

最后的动态规划解法，看似简单，但是琢磨了一天。