标签搜索

目 录CONTENT

文章目录

动态规划之正则表达.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 4 阅读 / 6,043 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

动态规划之正则表达

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

说明:

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

再次解决这道题!!!!!

方法一:DP table

在进行下面的处理之前,需要明确动态规划的几个步骤

状态

首先状态 dp 一定能自己想出来。
==dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配==

转移方程

怎么想转移方程?首先想的时候从已经求出了 dp[i-1][j-1] 入手,再加上已知 s[i]、p[j],要想的问题就是怎么去求 dp[i][j]。

已知 dp[i-1][j-1] 意思就是前面子串都匹配上了,不知道新的一位的情况。
那就分情况考虑,所以对于新的一位 p[j] s[i] 的值不同,要分情况讨论:

  1. 考虑最简单的 p[j] == s[i] : dp[i][j] = dp[i-1][j-1]
    然后从 p[j] 可能的情况来考虑,让 p[j]=各种能等于的东西

  2. p[j] == "." : dp[i][j] = dp[i-1][j-1]

  3. p[j] ==" * ":

前两种情况比较容易解决,接下来就对几种情况分别进行讨论:

处理「*」 通配符

第一个难想出来的点:怎么区分 ‘*’ 的两种讨论情况

首先给了 ‘*’,明白 ‘*’ 的含义是 匹配零个或多个前面的那一个元素,所以要考虑他前面的元素 p[j-1]‘*’ 跟着他前一个字符走,前一个能匹配上 s[i],‘*’ 才能有用,前一个都不能匹配上 s[i],‘*’ 也无能为力,只能让前一个字符消失,也就是匹配 0 次前一个字符

所以按照 p[j-1] 和 s[i] 是否相等,我们分为两种情况:

  1. p[j-1] != s[i] : dp[i][j] = dp[i][j-2]

这就是刚才说的那种前一个字符匹配不上的情况。

比如(ab, abc * )。遇到 ‘ * ’ 往前看两个,发现前面 s[i] 的 ab 对 p[j-2] 的 ab 能匹配,虽然后面是 ‘c*’,但是可以看做匹配 0 次 c,相当于直接去掉 ’c * ‘,所以也是 true。注意 (ab, abc**) 是 False。

  1. p[j-1] == s[i] or p[j-1] == "."

' * ' 前面那个字符,能匹配 s[i],或者 '*' 前面那个字符是万能的 .因为 '. *' 就相当于 '. .',那就只要看前面可不可以匹配就行。

比如 (##b , ###b *),或者 ( ##b , ### . * ) 只看 ### 后面一定是能够匹配上的。所以要看 b 和 'b *' 前面那部分 '##' 的地方匹不匹配。

第二个难想出来的点:怎么判断前面是否匹配

dp[i][j] = dp[i-1][j] // 多个字符匹配的情况	
or dp[i][j] = dp[i][j-1] // 单个字符匹配的情况
or dp[i][j] = dp[i][j-2] // 没有匹配的情况	

看 ### 匹不匹配,不是直接只看 ### 匹不匹配,要综合后面的 b* 来分析这三种情况是 or 的关系,满足任意一种都可以匹配上,同时是最难以理解的地方:

dp[i-1][j] 就是看 s 里 b 多不多, ### 和 ###b * 是否匹配,一旦匹配,s 后面再添个 b 也不影响,因为有 * 在,也就是 ###b 和 ###b *也会匹配

dp[i][j-1] 就是去掉 * 的那部分,###b 和 ###b 是否匹配,比如 qqb qqb

dp[i][j-2] 就是 去掉多余的 b *,p 本身之前的能否匹配,###b 和 ### 是否匹配,比如 qqb qqbb* 之前的 qqb qqb 就可以匹配,那多了的 b * 也无所谓,因为 b * 可以是匹配 00 次 b,相当于 b * 可以直接去掉了

三种满足一种就能匹配上。

为什么没有 dp[i-1][j-2] 的情况? 就是 ### 和 ### 是否匹配?因为这种情况已经是 dp[i][j-1] 的子问题。也就是 s[i]==p[j-1],则 dp[i-1][j-2]=dp[i][j-1]

最后来个归纳

如果 p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1];

如果 p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];

如果 p.charAt(j) == '*':

	如果 p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]
	
	如果 p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
				dp[i][j] = dp[i-1][j] 
				or dp[i][j] = dp[i][j-1] 
				or dp[i][j] = dp[i][j-2] 

完整代码:

public boolean isMatch(String s,String p){
            if (s == null || p == null) {
                return false;
            }
            boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
            dp[0][0] = true;//dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配
            for (int i = 0; i < p.length(); i++) { // here's the p's length, not s's
                if (p.charAt(i) == '*' && dp[0][i - 1]) {
                    dp[0][i + 1] = true; // here's y axis should be i+1
                }
            }
            for (int i = 0; i < s.length(); i++) {
                for (int j = 0; j < p.length(); j++) {
                    if (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)) {//如果是任意元素 或者是对于元素匹配
                        dp[i + 1][j + 1] = dp[i][j];
                    }
                    if (p.charAt(j) == '*') {
                        if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.') {//如果前一个元素不匹配 且不为任意元素
                            dp[i + 1][j + 1] = dp[i + 1][j - 1];
                        } else {
                            dp[i + 1][j + 1] = (dp[i + 1][j] || dp[i][j + 1] || dp[i + 1][j - 1]);
                            /*
                            dp[i][j] = dp[i-1][j] // 多个字符匹配的情况	
                            or dp[i][j] = dp[i][j-1] // 单个字符匹配的情况
                            or dp[i][j] = dp[i][j-2] // 没有匹配的情况
                             */
                            
                        }
                    }
                }
            }
            return dp[s.length()][p.length()];
        }

C++代码:

class Solution {
public:
    // 动态规划
    bool isMatch(string s, string p) {
        int ns = s.size();
        int np = p.size();

        if(p.empty()) //注意这里判断的写法,不能是if(p.empty() || s.empty());原因试一下就知道啦
            return s.empty();

        vector<vector<bool>> dp(ns+1, vector<bool>(np+1, false));

        //就是博客中的问题,怎么判断前面是否匹配,相当于提前把遇到‘*’的情况在dp[i][j - 2]
        //的情况先记录下来,后面使用,因为初始化的时候全部都是false,所以要提前处理
        dp[0][0] = true;
        for(int i = 1; i <= np; i++)
        {
            if(i-2 >= 0 && p[i-1] == '*' && p[i-2])
            {
                dp[0][i] = dp[0][i-2];
            }
        }
        
        for(int i = 1; i <= ns; i++)
        {
            for(int j = 1; j <= np; j++)
            {
                if(p[j-1] == s[i-1] || p[j-1] == '.')
                    dp[i][j] = dp[i-1][j-1];//万金油,直接相等

                if(p[j-1] == '*')
                {
                    bool zero, one;
                    if(j-2 >= 0)
                    {
                        zero = dp[i][j-2];//匹配0次,
                        one = (p[j-2] == s[i-1] || p[j-2] == '.') && dp[i-1][j];//匹配1次
                        dp[i][j] = zero || one;//有一个为真即可
                    }
                }
            }
        }
        return dp[ns][np];
    }
    

};

方法二: 动态规划

第⼀步, 我们暂时不管正则符号, 如果是两个普通的字符串进⾏⽐较, 如何
进⾏匹配? 我想这个算法应该谁都会写:

bool isMatch(string text, string pattern) {
	if (text.size() != pattern.size())
		return false;
	for (int j = 0; j < pattern.size(); j++) {
		if (pattern[j] != text[j])
			return false;
	} 
	return true;
}

然后, 稍微改造⼀下上⾯的代码, 略微复杂了⼀点, 但意思还是⼀样的,很容易理解吧:

bool isMatch(string text, string pattern) {
	int i = 0; // text 的索引位置
	int j = 0; // pattern 的索引位置
	while (j < pattern.size()) {
		if (i >= text.size())
			return false;
			
		if (pattern[j++] != text[i++])
			return false;
	} 
	// 相等则说明完成匹配
	return j == text.size();
}

如上改写, 是为了将这个算法改造成递归算法(伪码) :

def isMatch(text, pattern) -> bool:
	if pattern is empty: return (text is empty?)
		first_match = (text not empty) and pattern[0] == text[0]
	return first_match and isMatch(text[1:], pattern[1:])

处理点号「.」 通配符

点号可以匹配任意⼀个字符, 万⾦油嘛, 其实是最简单的, 稍加改造即可:

def isMatch(text, pattern) -> bool:
	if not pattern: return not text
		first_match = bool(text) and pattern[0] in {text[0], '.'}
	return first_match and isMatch(text[1:], pattern[1:])

处理「*」 通配符

星号通配符可以让前⼀个字符重复任意次数, 包括零次。 那到底是重复⼏次
呢? 这似乎有点困难, 不过不要着急, 我们起码可以把框架的搭建再进⼀
步:

def isMatch(text, pattern) -> bool:
	if not pattern: return not text
	first_match = bool(text) and pattern[0] in {text[0], '.'}
	if len(pattern) >= 2 and pattern[1] == '*':
		# 发现 '*' 通配符
	else:
		return first_match and isMatch(text[1:], pattern[1:])

星号前⾯的那个字符到底要重复⼏次呢? 这需要计算机暴⼒穷举来算, 假设
重复 N 次吧。 前⽂多次强调过, 写递归的技巧是管好当下, 之后的事抛给递归。 具体到这⾥, 不管 N 是多少, 当前的选择只有两个: 匹配 0 次、 匹
配 1 次。 所以可以这样处理:

if len(pattern) >= 2 and pattern[1] == '*':
	return isMatch(text, pattern[2:]) or \
	first_match and isMatch(text[1:], pattern)
	# 解释: 如果发现有字符和 '*' 结合,
	# 或者匹配该字符 0 次, 然后跳过该字符和 '*'
	# 或者当 pattern[0] 和 text[0] 匹配后, 移动 text

可以看到, 我们是通过保留 pattern 中的「*」 , 同时向后推移 text, 来实现
「」 将字符重复匹配多次的功能
。 举个简单的例⼦就能理解这个逻辑了。 假
pattern = a , text = aaa, 画个图看看匹配过程:

在这里插入图片描述

选择使⽤「备忘录」 递归的⽅法来降低复杂度

我将暴⼒解法和优化解法放在⼀起, ⽅便你对⽐,

# 带备忘录的递归
def isMatch(text, pattern) -> bool:
	memo = dict() # 备忘录
	def dp(i, j):
		if (i, j) in memo: return memo[(i, j)]
		if j == len(pattern): return i == len(text)
		first = i < len(text) and pattern[j] in {text[i], '.'}
		if j <= len(pattern) - 2 and pattern[j + 1] == '*':
			ans = dp(i, j + 2) or \
			first and dp(i + 1, j)
		else:
			ans = first and dp(i + 1, j + 1)
		memo[(i, j)] = ans
		return ans
	return dp(0, 0)
	
# 暴⼒递归
def isMatch(text, pattern) -> bool:
	if not pattern: return not text
	first = bool(text) and pattern[0] in {text[0], '.'}
	if len(pattern) >= 2 and pattern[1] == '*':
		return isMatch(text, pattern[2:]) or \
			first and isMatch(text[1:], pattern)
	else:
		return first and isMatch(text[1:], pattern[1:])
0

评论区