【剑指Offer刷题小记】正则表达式匹配（JAVA版）

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

问题分析：首先来看匹配完全的必要条件，就是模式串遍历完，同时原字符串也遍历完。据此，可以从前往后依次匹配直到匹配完全。由于’.’表示任意字符，因此可与任意字符匹配，可看作原串当前遍历到的字符。而’*‘的匹配结果则与‘*’前的字符有关，所以对于模式串当前字符下一位是不是‘*’，可分为两种情况：

（1）当前字符下一位不是‘*’：

        这里又分为两种情况：

        1º 当前字符匹配。那么原串和模式串都向后移一位，例如：

      2º 当前字符不匹配。那么直接返回false，例如：

（2）当前字符下一位不是‘*’：

    1º 当前字符不匹配。那么为了尽可能进行匹配，就要去除模式串的当前字符，去判断其后面的字符，也就是模式串向后移两位，例如：

    2º 当前字符匹配：此时有多种情况

          ·1.‘*’表示前面的字符出现0次：那么原串不移动，模式串向后移两位。如 aab/aa*ab  (加粗的为当前字符)

          ·2.‘*’表示前面的字符出现1次：那么原串向后移一位，模式串向后移两位。如aab/aa*b

          ·3.‘*’表示前面的字符出现n次（n>1）：那么原串向后移一位，模式串不移动。如aaa/aa*

    只要上面三种情况的任意一种匹配成功即可

代码截图：

这里要注意条件判断的先后顺序，首先判断索引是否超过长度，不然会导致越界的错误