算法之字符串——正则表达式匹配

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

难度 困难:worried:

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

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母以及字符 .*,无连续的 '*'

示例 1:
输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

示例 2:
输入:
s = “aa”
p = “a*“
输出: true
解释: 因为 ‘*‘ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此,字符串 “aa” 可被视为 ‘a’ 重复了一次。

示例 3:
输入:
s = “ab”
p = “.*”
输出: true
解释: “.*” 表示可匹配零个或多个(’*‘)任意字符(’.’)。

示例 4:
输入:
s = “aab”
p = “c*a*b”
输出: true
解释: 因为 ‘*’ 表示零个或多个,这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5:
输入:
s = “mississippi”
p = “mis*is*p*.”
输出: false

一开始的思路,,,,好吧没有思路:sob: 只能使用字符串中关于正则的匹配API,代码如下

class Solution {
    public boolean isMatch(String s, String p) {
        return s.matches(p);
    }
}

其实我们仔细考虑一下,无非就是分三种情况:raising_hand:

假设主串为 A,模式串为 B , A 的长度为 n ,B 的长度为 m ,关注正则表达式 B 的最后一个字符是谁,它有三种可能,正常字符,* 和 .(点),那针对这三种情况讨论即可,如下:

  • 如果 B 的最后一个字符是正常字符,那就是看 A[n-1] 是否等于 B[m-1],相等则看 A_{0..n-2}与 B_{0..m-2},不等则是不能匹配,这就是子问题。:clock1:

  • 如果 B 的最后一个字符是 .(点) ,它能匹配任意字符,直接看 A_{0..n-2}与 B_{0..m-2}:clock4:

  • 如果 B 的最后一个字符是 * ,它代表 B[m-2]=c 可以重复0次或多次,它们是一个整体 c*:clock7:

    • 情况一:A[n-1]是 0个 c,B 最后两个字符废了,能否匹配取决A_{0..n-1}和 B_{0..m-3}是否匹配
    • 情况二:A[n-1]是多个 c 中的最后一个(这种情况必须 A[n−1]=c 或者 c=’.’),所以 A 匹配完往前挪一个,B 继续匹配,因为可以匹配多个,继续看 A_{0..n-2}和 B_{0..m-1}是否匹配。

先来个某大神动态规划的思路:boom:

转移方程
f[i][j] 代表 A 的前 i 个和 B 的前 j 个能否匹配
对于前面两个情况,可以合并成一种情况 f[i][j] = f[i-1][j-1]
对于第三种情况,对于 c* 分为看和不看两种情况

  • 不看:直接砍掉正则串的后面两个, f[i][j] = f[i][j-2]
  • 看:正则串不动,主串前移一个,f[i][j] = f[i-1][j]

特判:需要考虑空串空正则

  • 空串和空正则是匹配的,f[0][0] = true
  • 空串和非空正则,不能直接定义 true 和 false ,必须要计算出来。(比如A=” “ ,B=abc*)
  • 非空串和空正则必不匹配,f[1][0]=…=f[n][0]=false
  • 非空串和非空正则,那肯定是需要计算的了。

大体上可以分为空正则和非空正则两种,空正则也是比较好处理的,对非空正则我们肯定需要计算,非空正则的三种情况,前面两种可以合并到一起讨论,第三种情况是单独一种,那么也就是分为当前位置是 * 和不是 * 两种情况了。

再来个递归代码,递归代码与上面的思路其实是一样的

package ddx.september.day29;

public class Normal_19 {
    public boolean isMatch(String s, String p) {
        if (s.length() == 0 ) {
            //主串为空
            if (p.length() % 2 != 0) {
                //模式串长度为奇数,则一定不匹配,因为抵消不了奇数
                //例如:"." , "ab*","abc"
                return false;
            } else {
                //长度为偶数,只需要判断偶数位上是不是*即可!
                int i = 1;
                while (i < p.length()) {
                    if (p.charAt(i) != '*') {
                        return false;
                    }
                    i += 2;
                }
                return true;
            }
        } else if (p.length() == 0) {
            //模式串为空
            return false;
        } else {
            char ch1 = s.charAt(0); //s的首位
            char ch2 = p.charAt(0); //p的首位
            char ch3 = 'a';         //p的下一位
            if(p.length() > 1){
                ch3 = p.charAt(1);
            }
            //照样分情况,看看是不是*
            if(ch3 != '*'){
                if(ch2 == ch1 || ch2 == '.'){
                    return  isMatch(s.substring(1),p.substring(1));
                }else{
                    //连正常字符和.都匹配不上
                    return false;
                }
            }else{
                //难点就在于ch3是 *
                //正常字符相等,或者是.
                //即选择或者不选择!!!
                //"aa"
                //"a*a"
                //上面两个字符串,碰到*可以选择,也可以不选择
                if(ch2 == ch1 || ch2 == '.'){
                    //前者是选择,后者是不选择
                    return isMatch(s.substring(1),p) || isMatch(s,p.substring(2));
                }else{
                    //连正常字符和.都匹配不上,那么ch2 和 ch3废了!!!!
                    return isMatch(s,p.substring(2));
                }
            }
        }
    }
}

算法之字符串——正则表达式匹配(二)

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!