[每日一道小算法（六十九）] [正则表达式] 正则表达式匹配（剑指offer）

亦凉 2023-07-08 02:41 42阅读 0赞

前言：  
正则表达式，使用起来很方便，减少了代码量，但是不是那么好想呀！加油吧，慢慢来！！！！

### 题目描述 ###

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

### 解题思路 ###

这道题，我主要是把所有情况都要考虑到。我们先来考虑特殊情况：

1.  当两个字符串都为空的时候，返回true。
2.  当第一个字符串不为空时，而第二个字符串空了，返回false。因为这样就无法匹配了。而如果第一个字符串空了，第二个字符串非空，还是可能匹配成功的。
3.  考虑完了特殊值，我们开始匹配第一个字符。这里是有两种可能。匹配成功或者匹配失败。但考虑到pattern下一个字符可能是’\*’。这里我们需要分两种情况讨论。
4.  pattern下一个字符不为’\*’ ：这种情况比较简单，直接匹配当前字符。如果匹配成功，则继续匹配下一个；如果匹配失败，直接返回false。这里匹配成功，除了两个字符相同的情况外，还有一种情况，就是pattern的当前字符为‘.’ ，同时str的当前字符不为‘\\0’。
5.  pattern下一个字符为‘ \* ’时，这里稍微复杂一些，因为 ’ \* '可以代表0个或多个。

*  当’\*'匹配0个字符时，str当前字符不变，pattern当前字符后移两位。跳过 ’ \* ’ 这个符号。
 *  当‘\*’匹配1个或多个时，str当前字符移向下一个，pattern当前字符不变。（这里匹配1个或多个可以看成一种情况，因为：当匹配一个时，由于str移到了下一个字符，而pattern字符不变，就回到了上边的情况a；当匹配多于一个字符时，相当于从str的下一个字符继续开始匹配）

### 代码样例 ###

package com.asong.leetcode.ZhengZe;
    
    /** * 正则表达式的匹配 */
    public class Solution { 
        public boolean match(char[] str, char[] pattern)
        { 
            //边界检查
            if(str==null&&pattern==null)
            { 
                return false;
            }else if(pattern==null)
            { 
                return false;
            }
            //定义两个指针分别指向str和pattern
            int indexOfStr = 0;
            int indexOfPattern = 0;
           return matchHelper(str,indexOfStr,pattern,indexOfPattern);
        }
        public boolean matchHelper(char[] str,int indexOfStr,char[] pattern,int indexOfPattern)
        { 
            //达到边界条件 指针索引完成
            if(indexOfStr == str.length && indexOfPattern==pattern.length)
            { 
                return true;
            }
            //如果indexOfPattern先到尾部则匹配失败
            if(indexOfPattern == pattern.length && indexOfStr<str.length)
            { 
                return false;
            }
            //pattern的第二个字符为‘*’，且第一个字符匹配，边界为模式指针未达到末尾
            if(indexOfPattern+1<pattern.length&&pattern[indexOfPattern+1]=='*')
            { 
                //第一个字符匹配 相等或者为 . 符号
                if((indexOfStr!=str.length&&str[indexOfStr]==pattern[indexOfPattern])||(indexOfStr!=str.length&&pattern[indexOfPattern]=='.')){ 
                    return matchHelper(str,indexOfStr,pattern,indexOfPattern+2)
                            ||matchHelper(str,indexOfStr+1,pattern,indexOfPattern+2)
                            ||matchHelper(str,indexOfStr+1,pattern,indexOfPattern);
                }else{ 
                    //第一个字符不匹配,pattern直接移动两位
                    return matchHelper(str,indexOfStr,pattern,indexOfPattern+2);
                }
            }
            //pattern的第二个字符不为'*',且第一个字符匹配
            if((indexOfStr!=str.length&&str[indexOfStr]==pattern[indexOfPattern])
                    ||(indexOfStr!=str.length&&pattern[indexOfPattern]=='.')){ 
                return matchHelper(str,indexOfStr+1,pattern,indexOfPattern+1);
            }else{ 
                //第一个字符不匹配
                return false;
            }
        }
    }