19 正则表达式匹配

牛客

描述

请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配

数据范围:

1. str 可能为空，且只包含从 a-z 的小写字母。
2. pattern 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 ''。
3. 0 <= str.length <= 20
4. 0 <= pattern.length <= 30
   要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

当遇到星号时有 3 种情况，匹配 1 次或匹配多次或匹配 0 次

public boolean match (String str, String pattern) {
        if(str==null || pattern==null) return false;
        return matchCore(str.toCharArray(), pattern.toCharArray(), 0, 0);
    }

private boolean matchCore(char[] str, char[] pattern, int i1, int i2){
    if(i1==str.length && i2==pattern.length) return true;
    if(i1!=str.length && i2==pattern.length) return false;
    if(i1>str.length) return false;

    if(i2+1<pattern.length && pattern[i2+1]=='*'){
        if(pattern[i2]=='.' || (i1<str.length && str[i1] == pattern[i2]) ){
            return matchCore(str, pattern, i1+1, i2+2)
                    || matchCore(str, pattern, i1+1, i2)
                    || matchCore(str, pattern, i1, i2+2);
        } else {
            return matchCore(str, pattern ,i1, i2+2);
        }
    }


    if((i1<str.length && str[i1] == pattern[i2]) || pattern[i2]=='.'){
        return matchCore(str, pattern, i1+1, i2+1);
    }
    return false;
}