剑指offer第五十二题。

题目描述

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

解题思路

这道题目实现起来很麻烦

当模式中的第二个字符不是*时：

这种情况比较简单：

①、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。

②、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。

而当模式中的第二个字符是*时：

这种情况就比较复杂了：

如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配，因为*是可以表示0个的。

如果字符串第一个字符跟模式第一个字符匹配，因为*是比较特殊的，他可以表示0个，也可以表示1个，也可以表示多个，我们需要考虑所有的情况，就有3种匹配方式：

①、模式后移2字符，相当于x*被忽略，字符不后移；

②、字符串后移1字符，模式后移2字符；

③、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；

对于.来说，表示任意一个字符，所以在进行上面的判断的时候，要额外判断一下是否有.这个情况，他可以与任意字符匹配的。

理顺了这个思路之后，下面就可以用代码来实线一波了。

我的答案

这一题给我的压力挺大的，虽然说思路可以理解，但是真正要写完整还是不容易的，我感觉这个程序可能还是存在一些问题的，但是牛客的案例比较少，所以可以通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        if (str == null || pattern == null) {
            return false;
        }
        
        int strIndex = 0;
        int patternIndex = 0;
        
        return match(str,strIndex,pattern,patternIndex);
    }
    
    private boolean match(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 < pattern.length-1 && pattern[patternIndex+1] == '*'){
            //如果匹配，匹配分为直接字符匹配和.匹配两种
            if((strIndex != str.length && str[strIndex] == pattern[patternIndex]) 
              || (strIndex != str.length && pattern[patternIndex] == '.')){
                //匹配了之后有三种选择的路，递归下去一直匹配到最后
                return match(str,strIndex,pattern,patternIndex+2) ||
                        match(str,strIndex+1,pattern,patternIndex+2) || 
                            match(str,strIndex+1,pattern,patternIndex);
            }else{
                //一开始跟*之前的字符就不匹配的话，就忽略这个*和*之前的字符，直接尝试匹配下个字符
                return match(str,strIndex,pattern,patternIndex+2);
            }
        }
        
        //如果第二个字符不是*，并且匹配的话就都往后移动一格
        if((strIndex != str.length && str[strIndex] == pattern[patternIndex]) 
              || (strIndex != str.length && pattern[patternIndex] == '.')){
            return match(str,strIndex+1,pattern,patternIndex+1);
        }
        
        return false;
    }
}