《剑指offer》—— 52. 正则表达式匹配（Java）

推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

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

public class Solution {
   
    public boolean match(char[] str, char[] pattern)
    {
   
        
    }
}

思路：

模式中的 ‘ . ’ 可以任意一个字符，这个比较好处理，加一个 || 判断即可。

难处理的是模式中的 ‘*’ ，‘*’ 表示它前面的字符可以出现任意次（包含0次）。

我们根据有和没有 ‘*’ ，分成两大类情况来处理。

Ⅰ、模式中的第二个字符是 “*” 时。

如果字符串中第一个字符与模式中第一个字符不匹配，字符串中的下标不后移，模式中的下标后移 2 位，相当于 x* 匹配 0 个字符，跳过模式中的这两个字符。
如果字符串中第一个字符与模式中第一个字符匹配，又可分为以下3种子情况来处理：

2.1 字符串中的下标不后移，模式中的下标后移 2 位，相当于 x* 还是匹配了 0 个字符；

2.2 字符串中的下标后移 1 位，模式中的下标后移 2 位，相当于 x* 匹配 1 个字符

2.3 字符串中的下标后移 1 位，模式中的下标不后移，相当于 x* 匹配了 1 个字符之后，还可能可以匹配串中的下一个字符

Ⅱ、模式中的第二个字符不是 “*” 时。

字符串中第 1 个和模式中第 1 个匹配，则字符串和模式中的下标都后移 1 位；
字符串中第 1 个和模式中第 1 个不匹配，直接返回 false。

实现：

public class Solution {
   
    public boolean match(char[] str, char[] pattern)
    {
   
        if (str == null  || pattern == null){
   
            return false;
        }
        
        //字符串中的下标
        int strIndex = 0;
        //模式中的下标
        int patternIndex = 0;
        
        return checkMatch(str, strIndex, pattern, patternIndex);
    }
    
    public boolean checkMatch(char[] str, int strIndex, char[] pattern, int patternIndex) {
   
        //如果字符串和模式长度都为0了，都到结尾了，则匹配成功，返回true
        if(strIndex == str.length && patternIndex == pattern.length) {
   
            return true;
        }
        //如果patter长度先为0，而字符串长度还没有为0，也就是模式先到结尾，而字符串还有没匹配的，说明匹配失败，返回false
        if (strIndex != str.length && patternIndex == pattern.length) {
   
            return false;
        }
        
        
        //模式第2个是 * ，如果字符串中第 1 个和模式中第 1 个匹配，分 3 中匹配模式； 如果第 1 个不匹配，模式后移 2 位；
        if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
   
            //字符串中第 1 个和模式中第 1 个匹配
            if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (strIndex != str.length && pattern[patternIndex] == '.')) {
   
                //3种匹配模式
                return checkMatch(str, strIndex, pattern, patternIndex + 2) //字符串中的下标不后移，模式中的下标后移 2 位，相当于 x* 匹配 0 个字符
                    // 字符串中的下标后移 1 位，模式中的下标后移 2 位，相当于 x* 匹配 1 个字符
                    || checkMatch(str, strIndex + 1, pattern, patternIndex + 2) 
                    // 字符串中的下标后移 1 位，模式中的下标不后移，相当于 x* 匹配了 1 个字符之后，还可能可以匹配串中的下一个字符
                    || checkMatch(str, strIndex + 1, pattern, patternIndex); 
            } else {
    //字符串中第 1 个和模式中第 1 个不匹配，字符串中的下标不后移，模式中的下标后移 2 位，相当于 x* 匹配 0 个字符，跳过模式中的这两个字符。
                return checkMatch(str, strIndex, pattern, patternIndex + 2);
            }
        }
        
        
        //模式第2个不是 * ，且字符串中第 1 个和模式中第 1 个匹配，则都后移 1 位； 
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (strIndex != str.length && pattern[patternIndex] == '.')) {
   
            return checkMatch(str, strIndex + 1, pattern, patternIndex + 1);
        }
        
        //模式第2个不是 * ，且字符串中第 1 个和模式中第 1 个不匹配，直接返回 false。
        return false;
        
    }
    
}