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

    正则表达式的匹配 - 图1

    在匹配字符串时，每次我们拿出匹配字符串中的一个字符与模式字符串中的字符进行匹配，匹配字符与模式字符之间的匹配分为三种情况：

    1. 当前要匹配的模式字符的下一个字符不是 '*'，那么当匹配字符与模式字符相同或者模式字符为 '.' 时都算匹配成功，当匹配成功时，进行匹配下一个字符

    正则表达式的匹配 - 图2

    1. 模式字符的后一位为 '*'，并且当前字符匹配时，因为 '*' 代表任意次，它可以有以下三种匹配行为 正则表达式的匹配 - 图3
      • 选择只匹配一个 正则表达式的匹配 - 图4
      • 选择不匹配 正则表达式的匹配 - 图5
      • 选择匹配多个 正则表达式的匹配 - 图6

    上述三种行为，只要有一种情况匹配最后匹配成功，那么就匹配成功，所以它们之间是或的关系。

    1. 模式字符的后一位为 '*'，并且当前字符不匹配时 正则表达式的匹配 - 图7

    当匹配字符与模式字符匹配成功时，才继续进行匹配，当匹配字符串和模式字符串同时匹配完毕时，那么说匹配字符串与模式字符串匹配成功了，代码如下

    1. public class Match {
    2.     public static boolean match(char[] str, char[] pattern) {
    3.         if (str == null || pattern == null) {
    4.             return false;
    5.         }
    7.         // 匹配字符串和模式字符串都从起始字符进行匹配
    8.         return matchCore(str, 0, pattern, 0);
    9.     }
    11.     private static boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
    12.         // 二者同时匹配完毕时，才匹配成功
    13.         if (strIndex == str.length  && patternIndex == pattern.length) {
    14.             return true;
    15.         }
    17.         // 模式字符串匹配完毕，但是匹配字符串还有字符没有匹配
    18.         if (strIndex != str.length && patternIndex == pattern.length) {
    19.             return false;
    20.         }
    22.         // 匹配字符串匹配完毕，但是模式字符串还有字符未被匹配
    23.         if (strIndex == str.length && patternIndex != pattern.length) {
    24.             return false;
    25.         }
    27.         // 如果下一个字符为 *
    28.         if ((patternIndex + 1) < pattern.length && pattern[patternIndex + 1] == '*') {
    29.             // 匹配时有三种选择
    30.             if (pattern[patternIndex] == str[strIndex] || pattern[patternIndex] == '.') {
    31.                 boolean result = matchCore(str, strIndex + 1, pattern, patternIndex + 2)
    32.                 || matchCore(str, strIndex + 1, pattern, patternIndex)
    33.                 || matchCore(str, strIndex, pattern, patternIndex + 2);
    34.                 return result;
    35.             } else {
    36.                 // 当前字符不匹配，匹配字符向后移两个字符
    37.                 return matchCore(str, strIndex, pattern, patternIndex + 2);
    38.             }
    39.         }
    41.         // 第二个字符不为*，这时如果匹配字符与模式字符相同或者模式字符为 .都算匹配成功
    42.         // 这时匹配字符和模式字符都向后移一个字符
    43.         if (str[strIndex] == pattern[patternIndex] || (pattern[patternIndex] == '.')) {
    44.             return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
    45.         }
    47.         return false;
    48.     }
    50.     public static void main(String[] args) {
    51.         char[] str = "aaa".toCharArray();
    53.         char[] pattern1 = "a.a".toCharArray();
    54.         System.out.println(match(str, pattern1)); // true
    56.         char[] pattern2 = "ab*ac*a".toCharArray();
    57.         System.out.println(match(str, pattern2)); // true
    59.         char[] pattern3 = "aa.a".toCharArray();
    60.         System.out.println(match(str, pattern3)); // false
    62.         char[] pattern4 = "ab*a".toCharArray();
    63.         System.out.println(match(str, pattern4)); // false
    65.     }
    66. }