正则表达式匹配

《剑指offer》面试题19：正则表达式匹配

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

思路：每次从字符串中拿出一个字符和模式中的字符去匹配，如果模式中的字符是‘.’，那么可以匹配字符串中的任意字符。如果模式中的字符不是'.'，并且字符串中的字符和模式中的字符相等，则匹配成功。继续匹配后面的字符。
如果模式中的第二个字符不是''，如果字符串中的第一个字符和模式中的第一个字符匹配，则在字符串和模式上都向后移动一个字符，然后匹配剩下的字符串和模式。否则返回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个字符继续匹配
        } else {
            // * 和它前面的字符匹配了0个
            return matchCore(str,strIndex,pattern,patternIndex + 2);
        }
    } else {
        // 模式第二个字符不是 *，如果字符串第一个字符和模式第一个字符相匹配，则继续匹配后面的字符
        if ((strIndex < str.length && str[strIndex] == pattern[patternIndex]) || (strIndex < str.length && pattern[patternIndex] == '.')) {
            return matchCore(str,strIndex + 1,pattern,patternIndex + 1);
        }
    }
    return false;
}