LeetCode真题-通配符匹配

一秉

题目描述
请实现支持'.'and'*'.的通配符模式匹配
'.' 可以匹配任何单个字符。
'*' 可以匹配任何字符序列（包括空序列）。
匹配应该覆盖整个输入字符串（而不是部分）。
函数声明为：bool isMatch(const char *s, const char *p)
下面给出一些样例：
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
代码实现：
public class Solution {
    public boolean isMatch(String s, String p) {
        int len1=s.length();
        int len2=p.length();
        char[] s1=s.toCharArray();
        char[] p1=p.toCharArray();
        boolean[][] dp=new boolean[len1+1][len2+1];
        dp[0][0]=true;
        for(int i=1;i<=len2;i++)
            if(p1[i-1]=='*')
                dp[0][i]=dp[0][i-2];
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(p1[j-1]=='.'||p1[j-1]==s1[i-1]){
                    dp[i][j]=dp[i-1][j-1];
                }
                else if(p1[j-1]=='*'){
                    if(j!=1&&(p1[j-2]!='.'&&p1[j-2]!=s1[i-1]))
                        dp[i][j]=dp[i][j-2];
                        else
                            dp[i][j]=dp[i][j-2]||dp[i][j-1]||dp[i-1][j];
                    }
                }
            }
            return dp[len1][len2];
        }
    }