【剑指Offer】19. 正则表达式匹配

曾经终败给现在 2022-11-25 10:23 198阅读 0赞

[NowCoder][]

## 题目描述 ##

请实现一个函数用来匹配包括 ‘.’ 和 ‘\*’ 的正则表达式。模式中的字符 ‘.’ 表示任意一个字符，而 ‘\*’ 表示它前面的字符可以出现任意次（包含 0 次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串 “aaa” 与模式 “a.a” 和 “ab\*ac\*a” 匹配，但是与 “aa.a” 和 “ab\*a” 均不匹配。

## 解题思路 ##

应该注意到，’.’ 是用来当做一个任意字符，而 ‘\*’ 是用来重复前面的字符。这两个的作用不同，不能把 ‘.’ 的作用和 ‘\*’ 进行类比，从而把它当成重复前面字符一次。

### 递归 ###

假设主串为s，长度为sn， 模式串为p，长度为pn，对于模式串p当前的第i位来说，有’正常字符’、’\*’、’.'三种情况。我们针对这三种情况进行讨论：

如果p\[i\]为正常字符， 那么我们看s\[i\]是否等于p\[i\], 如果相等，说明第i位匹配成功,接下来看s\[i+1…sn-1\] 和 p\[i+1…pn-1\]

如果p\[i\] 为’.’, 它能匹配任意字符，直接看s\[i+1…sn-1\] 和 p\[i+1…pn-1\]

如果p\[i\] 为’\*’， 表明p\[i-1\]可以重复0次或者多次，需要把p\[i-1\] 和 p\[i\]看成一个整体.

如果p\[i-1\]重复0次，则直接看s\[i…sn-1\] 和 p\[i+2…pn-1\]  
如果p\[i-1\]重复一次或者多次,则直接看s\[i+1…sn-1\] 和p\[i…pn-1\]，但是有个前提：s\[i\]= =p\[i\] 或者 p\[i\] == ‘.’  
三种情况如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70 3]  
显然上述的过程可以递归进行计算。  
则递归三部曲为：

递归函数功能：match(s, p) -> bool, 表示p是否可以匹配s

递归终止条件：

如果s 和 p 同时为空，表明正确匹配  
如果s不为空，p为空，表明，不能正确匹配  
如果s为空，p不为空，需要计算，不能直接给出结果  
下一步递归：

对于前面讨论的情况1，2进行合并，如果s = = p || p == ‘.’,则match(s+1, p+1)

对于情况3，如果重复一次或者多次，则match(s+1,p),如果重复0次，则match(s, p+2)

解法有很多，有非递归的写法，动态规划以及递归，感觉这个题属于难题了，能做出来即可，难度高还追求多种解法不是本菜鸟的风格。嗯，所以我选择在看懂递归代码后，做个总结。  
代码思路：  
  首先肯定是两个指针，一个在给定字符串上动，一个在模板上动。如果匹配肯定都向后移动，但此时由于有两个特殊符号捣乱，因此比较特殊。  
  首先分析’.‘的情况。当我们比较两个指针指的字符时，模板的字符是’.’，那么可以让两个指针同时后移。这个情况简单，就默认相等嘛。换句话说，本题只用考虑有没有’\*'就可以了。

考虑’*‘的相关情况情况。我们比较两个指针的字符时，如果字符串是s指针，模板是P指针指向某个字符。那么P的下一个字符不是’*‘时，那么就是最普通的情况，直接都往后移一位。即s++,p++。  
  分析此时有’*‘时，注意此时，p+1指向了一个’*’。那么我们怎么移动指针呢。

方式1：出现了’*’，而且s和p指向的都不相等，就相当于模板中’*‘前面的出现了0次，此时必须让p指针向后移动2位，让模板跳过’*'即可。（对于abge和ac*mn，s指b，p指c，则让p指向m，即p+2。认为c没出现过）  
方式2：出现了’*’，而且s和p指向的相等（这里的相等可以是真正的相等，也可以是’.'标记的相等）。比如abcd和ab*cf，其中s和p都指向了b。此时应该s+1和p+2。比如abbcd和ab*cf，其中s和p都指向了b。由于b出现了多次，应该不着急移动p，所以此时s+1即可。比如"cba","cb*a*a"，我也可以认为，p指向的第1个a没出现过，即使你相等。因此此时可以s不动，p+2。  
  可以看到，方式2中其实又分为3种情况，而实际上，我们无法区分具体应该选择哪一个方式处理，所以只能将3个方法同时利用或运算并列起来。其中方式2的第3种处理很不容易想到，因为就算相等了，我还是认为你不相等，忽略你，是真的牛。  
  再次捋一遍。由于把真正的相等和’.‘标记的相等并成一类，就只用考虑’*’。如果不出现星号，就常规比较，常规比较肯定出现相等或者不等两类。如果出现星号，就考虑两个指针指的是否相等，不等，则p指针直接+2。两个指针相等，则有3种情况并列处理。再在这些判断中，加入对应边界条件，就可以很容易理解并写出代码了。

public class Solution { 
        public boolean match(char[] str, char[] pattern)
        { 
            if (str == null || pattern == null)
                return false;
            return matchCore(str, 0, pattern, 0);
        }
        private boolean matchCore(char[] str, int s, char[] pattern, int p) { 
            //下面4行是递归结束标志，两个指针都指到了最后，才是匹配，否则不匹配
            if (s == str.length && p == pattern.length)
                return true;
            if (s < str.length && p == pattern.length)
                return false;
     
            //虽然比的是P位置的，但是P后面出现*时，规则需要改变。
            if (p + 1 < pattern.length && pattern[p + 1] == '*') { 
                //出现了*，并且s和P指向的相同，3种情况并列
                if ((s < str.length && pattern[p] == '.')
                        || (s < str.length && pattern[p] == str[s])) { 
                    return matchCore(str, s, pattern, p + 2)
                            || matchCore(str, s + 1, pattern, p)
                            || matchCore(str, s + 1, pattern, p + 2);
                } else { //出现了*，并且s和p指向的不同，那就把*前面的字符理解出现了0次，p+2
                    return matchCore(str, s, pattern, p + 2);
                }
            }
            //说明P后面不是*，那么就进行常规判断。相同就分别给指针+1
            if (s < str.length && (pattern[p] == str[s] || pattern[p] == '.'))
                return matchCore(str, s + 1, pattern, p + 1);
            //p后面又不是*，也没有.给你撑腰，你还敢出现不同，那必然false
            return false;
        }
    }

### 标记 ###

public boolean match(char[] str, char[] pattern) { 
    
        int m = str.length, n = pattern.length;
        boolean[][] dp = new boolean[m + 1][n + 1];
    
        dp[0][0] = true;
        for (int i = 1; i <= n; i++)
            if (pattern[i - 1] == '*')
                dp[0][i] = dp[0][i - 2];
    
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')
                    dp[i][j] = dp[i - 1][j - 1];
                else if (pattern[j - 1] == '*')
                    if (pattern[j - 2] == str[i - 1] || pattern[j - 2] == '.') { 
                        dp[i][j] |= dp[i][j - 1]; // a* counts as single a
                        dp[i][j] |= dp[i - 1][j]; // a* counts as multiple a
                        dp[i][j] |= dp[i][j - 2]; // a* counts as empty
                    } else
                        dp[i][j] = dp[i][j - 2];   // a* only counts as empty
    
        return dp[m][n];
    }

### 正则 ###

public class Solution { 
        public boolean match(char[] str, char[] pattern)
        { 
            return new String(str).matches(new String(pattern));
        }
    }

[NowCoder]: https://www.nowcoder.com/practice/45327ae22b7b413ea21df13ee7d6429c?tpId=13&tqId=11205&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=bennyrhys@163.com
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70]: /images/20221124/d3f79146bca74c0abd8efc339e54b5eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70 1]: /images/20221124/5451b4002a514ee794cb63e5cf301eda.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70 2]: /images/20221124/bdc153ac0d104263b7ad58988944cae5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70 3]: /images/20221124/3cf8e4133acc46598b1da438393ae871.png