正则表达式匹配

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

解题思路

  1. 对于 * 有三种匹配模式:匹配0次,1次以及多次
  2. 对于 . 只有一种匹配模式

    public boolean match(char[] str, char[] pattern) {
    if (str.length == 0 && new String(pattern).replaceAll(".\\*", "").length() == 0) {
        return true;
    }
    
    return match(str, 0, pattern, 0);
    }
    
    private boolean match(char[] str, int i, char[] pattern, int j) {
    if (i == str.length && j == pattern.length) {
        return true;
    }
    
    if (j >= pattern.length) return false;
    
    if (j + 1 < pattern.length && pattern[j + 1] == '*') {
        if ((i < str.length && pattern[j] == str[i]) || (pattern[j] == '.' && i != str.length)) {
            return match(str, i + 1, pattern, j + 2)
                    || match(str, i + 1, pattern, j)
                    || match(str, i, pattern, j + 2);
        } else {
            return match(str, i, pattern, j + 2);
        }
    }
    
    if ((i < str.length && pattern[j] == str[i])
            || (pattern[j] == '.' && i != str.length)) {
        return match(str, i + 1, pattern, j + 1);
    }
    
    return false;
    }