递归

class Solution {
    public boolean isMatch(String s, String p) {
        return helper(s,0,p,0);
    }

    private boolean helper(String s, int curs, String p, int curp) {
        //两个都匹配完了肯定是对的
        if(curs>=s.length() && curp>=p.length()) return true;
        //正则完了字符串还没完肯定是错的
        if(curs<s.length() && curp>=p.length()) return false;
        if(curp+1<p.length() && p.charAt(curp+1)=='*'){
            //下一个是*
            if(curs>=s.length()){
                //字符串已经匹配完了,当前的x*取0个x，还不一定对错
                return helper(s,curs,p,curp+2);
            }else{
                if(s.charAt(curs)==p.charAt(curp) || p.charAt(curp)=='.'){
                    //如果正则和字符串的字符相等或者为.时，要看三种情况之一，
                    //一种是当前x*取0个x（可能后面还有x*），
                    //一种是当前字符匹配，之后的正则依然用当前的.
                    //一种是当前正则x*就只匹配当前字符
                    return helper(s,curs,p,curp+2) || helper(s,curs+1,p,curp) || helper(s,curs+1,p,curp+2);
                }else{
                    //如果当前正则和当前字符没法匹配，那么只能看下一个正则是否匹配
                    return helper(s,curs,p,curp+2);
                }
            }
        }else{
            if(curs>=s.length()) {
                //如果当前正则不是x*，且字符串匹配完了，那么一定不匹配
                return false;
            }else{
                if(s.charAt(curs)==p.charAt(curp) || p.charAt(curp)=='.'){
                    //字符和正则各用掉一个
                    return helper(s,curs+1,p,curp+1);
                }else{
                    //只要有一个不匹配就是错
                    return false;
                }
            }
        }
    }
}

动归

public boolean isMatch(String s, String p) {
        if(s==null || p==null) return false;
        int sLen=s.length(),pLen=p.length();
        //dp[i][j]表示字符串substring(0,i)是否可以匹配正则表达式substring(0,j)
        boolean[][] dp=new boolean[sLen+1][pLen+1];
        //初始化边界，特别是空字符串和非空正则的匹配
        dp[0][0]=true;
        for(int i=1;i<=pLen;i++){
            if(p.charAt(i-1)=='*' && dp[0][i-2]){
                dp[0][i]=true;
            }
        }
        for(int si=1;si<=sLen;si++){
            //s中第si-1个字符
            char sc=s.charAt(si-1);
            for(int pi=1;pi<=pLen;pi++){
                //p中第pi-1个字符
                char pc=p.charAt(pi-1);
                if(pc=='*'){
                    //要看前一个pcpre的情况
                    char pcpre=p.charAt(pi-2);
                    if(pcpre==sc || pcpre=='.'){
                        //如果pcpre可以匹配sc，那么三种情况满足一种就可以
                        dp[si][pi]=dp[si-1][pi]||dp[si][pi-2]||dp[si-1][pi-2];
                    }else{
                        //pcpre和sc不匹配，那么只能忽略掉当前的正则，看前一个正则是不是匹配，由于是x*型的，所以要-2
                        dp[si][pi]=dp[si][pi-2];
                    }
                }else{
                    if(pc==sc || pc=='.'){
                        dp[si][pi]=dp[si-1][pi-1];
                    }
                    //这里的else一定是false就不写了
                }
            }
        }
        return dp[sLen][pLen];
    }