《劍指offer》面試題19：正則表達式匹配

題目：請實現(xiàn)一個函數(shù)用來匹配包括'.'和''的正則表達式。模式中的字符'.'表示任意一個字符，而''表示它前面的字符可以出現(xiàn)任意次（包含0次）。 在本題中，匹配是指字符串的所有字符匹配整個模式。例如，字符串"aaa"與模式"a.a"和"abaca"匹配，但是與"aa.a"和"ab*a"均不匹配。

思路：每次從字符串中拿出一個字符和模式中的字符去匹配，如果模式中的字符是‘.’，那么可以匹配字符串中的任意字符。如果模式中的字符不是'.'，并且字符串中的字符和模式中的字符相等，則匹配成功。繼續(xù)匹配后面的字符。
如果模式中的第二個字符不是''，如果字符串中的第一個字符和模式中的第一個字符匹配，則在字符串和模式上都向后移動一個字符，然后匹配剩下的字符串和模式。否則返回false。
如果模式中的第二個字符是''。有多種情況，一種是模式直接向后移動2個字符。相當于''和它前面的字符匹配了0個。如果字符串中的第一個字符和模式的第一個字符相匹配，則模式可以選擇向后移動2個字符，相當于''和它前面的字符匹配了一個。也可以模式保持不變，相當于'*'和它前面的字符匹配了多個。

代碼如下：

public boolean match(char[] str,char[] pattern) {
    if (str == null || pattern == null) {
        return false;
    }
    return matchCore(str,0,pattern,0);
}

public boolean matchCore(char[] str,int strIndex,char[] pattern,int patternIndex) {
    // 模式和字符串同時匹配完。則匹配成功
    if (strIndex == str.length && patternIndex == pattern.length) {
        return true;
    }
    // 模式先匹配完，則匹配失敗
    if (strIndex < str.length && patternIndex == pattern.length) {
        return false;
    }
    // 模式第二個字符為 *
    if (((patternIndex + 1) < pattern.length) && pattern[patternIndex + 1] == '*') {
        // 如果模式第一個字符和字符串第一個字符匹配
        if ((strIndex < str.length && str[strIndex] == pattern[patternIndex]) || (strIndex < str.length && pattern[patternIndex] == '.')) {
            return matchCore(str,strIndex,pattern,patternIndex + 2) || //匹配0個字符
                   matchCore(str,strIndex + 1,pattern,patternIndex + 2) || // 僅匹配1個字符
                   matchCore(str,strIndex + 1,pattern,patternIndex); // 匹配1個字符繼續(xù)匹配
        } else {
            // * 和它前面的字符匹配了0個
            return matchCore(str,strIndex,pattern,patternIndex + 2);
        }
    } else {
        // 模式第二個字符不是 *，如果字符串第一個字符和模式第一個字符相匹配，則繼續(xù)匹配后面的字符
        if ((strIndex < str.length && str[strIndex] == pattern[patternIndex]) || (strIndex < str.length && pattern[patternIndex] == '.')) {
            return matchCore(str,strIndex + 1,pattern,patternIndex + 1);
        }
    }
    return false;
}