正则表达式匹配

请实现一个函数用来匹配包括’.‘和’*'的正则表达式。

模式中的字符’.‘表示任意一个字符，而’*'表示它前面的字符可以出现任意次（含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。

例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配。

样例输入：s="aa"p="a*"输出:true

时间复杂度O(n^2)

class Solution {    public boolean isMatch(String s, String p) {        if(s == null || p== null || (s.length()!=0 && p.length()==0)) {            return false;        }        char[] str = s.toCharArray();        char[] pat = p.toCharArray();        return matchCore(str,0,pat,0);    }    private boolean matchCore(char[] str, int indexOfStr, char[] pattern, int indexOfPattern) {        if (indexOfStr == str.length && indexOfPattern == pattern.length){            return true;}        if (indexOfStr < str.length && indexOfPattern == pattern.length) {            return false;        }        if (indexOfPattern + 1 < pattern.length && pattern[indexOfPattern + 1] == '*') {            if ((indexOfStr < str.length && pattern[indexOfPattern] == '.')                    || (indexOfStr < str.length && pattern[indexOfPattern] == str[indexOfStr])) {                return matchCore(str, indexOfStr, pattern, indexOfPattern + 2)                        || matchCore(str, indexOfStr + 1, pattern, indexOfPattern)                        || matchCore(str, indexOfStr + 1, pattern, indexOfPattern + 2);            } else {                return matchCore(str, indexOfStr, pattern, indexOfPattern + 2);            }        }        if (indexOfStr < str.length && (pattern[indexOfPattern] == str[indexOfStr] || (pattern[indexOfPattern] == '.'))){            return matchCore(str, indexOfStr + 1, pattern, indexOfPattern + 1);        }        return false;    }}

时间复杂度O(nm)

class Solution {    static boolean[][] dp;    static int n,m;    public static boolean isMatch(String s, String p){        char[] ss = s.toCharArray();        char[] ps = p.toCharArray();        dp = new boolean[ss.length + 1][ps.length + 1];        n = ss.length;        m = ps.length;        dp[n][m] = true;        return dp(0,0,ss,ps);    }    private static boolean dp(int i, int j, char[] ss, char[] ps){        if (dp[i][j]){            return dp[i][j];        }        // 模式串匹配完成，判断是否匹配完字符串        if (j == m){            return dp[i][j] = i == n;        }        // 出现两个串字符相同或者模式串为'.'时则为true        boolean firstMatch = i < n && (ss[i] == ps[j] || ps[j] == '.');        boolean ans;        if (j + 1 < m && ps[j + 1] == '*'){            // j + 2意味着 *号和之前的一个元素没有被匹配到则跳过            ans = dp(i,j + 2, ss, ps) || firstMatch && dp(i + 1, j, ss, ps);        }else {            ans = firstMatch && dp(i + 1, j + 1, ss, ps);        }        return dp[i][j] = ans;    }}