正则表达式匹配-剑指Offer

正则表达式匹配

题目描述

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

思路

1. 当遇到'.'的时候，任何字符都匹配，好处理
2. 当遇到'*'的时候，有三种可能：
   1. 出现0次，不匹配
   2. 出现一次，只匹配一次
   3. 匹配多次
3. 这是一个递归的过程。

代码

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

    }
    public boolean matchCore(char[] str, int strP, char[] pattern, int patP) {
        if (strP == str.length &&  patP == pattern.length) {
            return true;
        }
        if ((strP < str.length && patP == pattern.length)) {
            return false;
        }
        if ((patP + 1 < pattern.length) && pattern[patP + 1] == '*') {
            if ((strP < str.length && str[strP] == pattern[patP]) || (pattern[patP] == '.' && strP < str.length)) {
                return matchCore(str, strP + 1, pattern, patP + 2)
                        || matchCore(str, strP, pattern, patP + 2)
                        || matchCore(str, strP + 1, pattern, patP);
                        // 匹配一次
                        // 匹配0次
                        // 匹配多次
            } else {
                return matchCore(str, strP, pattern, patP + 2);
                // 匹配0次
            }
        }
        if ((strP < str.length && pattern[patP] == str[strP]) || (pattern[patP] == '.' && strP < str.length)) {
            return matchCore(str, strP + 1, pattern, patP + 1);
            // 匹配一次
        }
        return false;
    }
}