LeetCode_10: Regular Expression Matching - LeetCode

# 引言

题目链接：https://leetcode.com/problems/regular-expression-matching/description/

# 题目大意

给定一个输入字符，和一个匹配模式 p, 实现正则表达式的匹配，匹配模式支持 '.' 和 '*'

'.' 匹配任何单个的字符

'*' 匹配前一个元素 n 次 (n>=0)

要求模式 p 的匹配覆盖整个输入字符串，而不是部分匹配

Example

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

# 题解

# 方法一：递归求解

由于 * 在模式匹配中可以匹配前一个字符 0 或者多次，稍后单独讨论，先思考只有 . 的情况

递归返回条件：模式串 p 为空，当 p 为空时，返回当前串是否为空即可
在不考虑 * 时，匹配按位进行，由 s 和 p 当前位置的相等性决定整体相等性，即当前比对达成条件 s[0] == p[0] || p[0] == '.' 即可，此时将 s 和 p 的当前字符一同去掉递归调用即可，达到递归返回条件后返回堆栈结果

接下来考虑带有 * 的情况

将上述条件 2 作为默认条件判断入口，依据 * 的定义其对于匹配的影响受到模式串当前位置前一个位置的影响，带 * 号判断入口如下 p.size() > 1 && p[1] == '*'

考虑一下两种情况：

* 前模式串字符和当前匹配字符不相等：此时只有当前匹配字符匹配零次可以确保匹配继续下去，否则直接失败，此时模式串 p 前进两位即 isMatch(s, p.substr(2))
* 前模式串字符和当前匹配字符相等：即 * 前模式串字符和当前匹配字符满足条件 s[0] == p[0] || p[0] == '.' , 此时可以匹配当前 s 字符 0 次或多次，0 次匹配和第一种情况状态重复参考 1 即可。关于多次匹配拆分为多个一次匹配递归调用即可，当进行一次匹配，默认 s 前进一个字符，模式串不进行位移递归准备下一次匹配即 isMatch(s.substr(1), p) , 当递归达成条件 1 时，当前 * 号匹配完成

# 方法二：动态规划

当匹配串 s 和模式串 p 匹配完成时，最后一次匹配所得结果和之前所有匹配整体结果共同决定匹配是否达成，即当前匹配后整体结果是本地匹配在之前状态上的叠加，因此我们可以同步不断缩减这个状态叠加过程达到简化问题规模的目的。

对于 s 和 p, 作如下设定，s 的最后一个字符为 x, p 的最后两个字符为 yz (由于 * 号的匹配需要前一个字符共同作用), === 代表状态匹配

s = s'x
p = p'yz

下面开始分析

z != '*'
1. 如果 x===z (x==z || z=='.') , 若 s'===p'y , 则 s===p
z == '*' (此时结合 y 一同考虑)
1. x != y, 则 yz 共同决定匹配 x 零次，若 s'===p' , 则 s===p
2. x == z, 此时考虑 yz 匹配 x 的次数
  1. 匹配 0 次：即 yz 跳过，若 s'x===p' , 则 s===p
  2. 匹配 1 次：即 yz 匹配 x, 若 s'===p' , 则 s===p
  3. 匹配多次：yz 反复利用继续匹配，若 s'===p'yz' , 则 s===p

设定 dp[i][j] 表示 s[0,i) 和 p[0,j) 是否匹配

则分析对应 dp 方程如下：

if s[i - 1] == p[j - 1] || p[j - 1] == '.'
    dp[i][j] = dp[i - 1][j - 1];
 if (p[j - 1] == '*')
    // match 0,1,more
     dp[i][j] = dp[i][j - 2];
     dp[i][j] = dp[i - 1][j - 2];
     dp[i][j] = dp[i - 1][j];

复杂度 O(m*n) , 递归进行堆栈调用时中间状态会有重复计算，时间上相对耗时更多

# AC 代码

c++ 递归版本

	class Solution
	{
	public:
	bool isMatch(string s, string p)
	{
	if (p.empty())
	{
	return s.empty();
	}
	if (p.size() > 1 && p[1] == '*')
	{
	return isMatch(s, p.substr(2)) \|\| (!s.empty() && (s[0] == p[0] \|\| p[0] == '.') && isMatch(s.substr(1), p));
	}
	else
	{
	return !s.empty() && (s[0] == p[0] \|\| p[0] == '.') && isMatch(s.substr(1), p.substr(1));
	}
	}
	};

c++ dp 版本

	class Solution
	{
	public:
	bool isMatch(string s, string p)
	{
	int lens = s.length();
	int lenp = p.length();
	bool dp[1001][1001];
	memset(dp, false, sizeof(dp));
	dp[0][0] = true;
	for (int i = 0; i <= lens; ++i)
	{
	for (int j = 1; j <= lenp; ++j)
	{
	if (i > 0 && (s[i - 1] == p[j - 1] \|\| p[j - 1] == '.'))
	{
	dp[i][j] = dp[i - 1][j - 1];
	}
	else
	{
	if (p[j - 1] == '*')
	{
	// match 0.1.more
	dp[i][j] = dp[i][j - 2]
	\|\| (i > 0 && j > 1 && dp[i - 1][j - 2] && (s[i - 1] == p[j - 2] \|\| p[j - 2] == '.'))
	\|\| (i > 0 && j > 1 && dp[i - 1][j] && (s[i - 1] == p[j - 2] \|\| p[j - 2] == '.'));
	}
	}
	}
	}
	return dp[lens][lenp];
	}
	};

go 版本

	func isMatch(s string, p string) bool {
	lens, lenp := len(s), len(p)
	var dp[1001][1001] bool
	dp[0][0] = true
	for i := 0; i <= lens; i++ {
	for j := 1; j <= lenp; j++ {
	if i > 0 && (s[i-1] == p[j-1] \|\| p[j-1] == '.') {
	dp[i][j] = dp[i-1][j-1]
	} else{
	if j > 1 && p[j-1] == '*' {
	dp[i][j] = dp[i][j-2] \|\|
	(i > 0 && dp[i - 1][j - 2] && (s[i - 1] == p[j - 2] \|\| p[j - 2] == '.')) \|\|
	(i > 0 && dp[i - 1][j] && (s[i - 1] == p[j - 2] \|\| p[j - 2] == '.'))
	}
	}
	}
	}
	return dp[lens][lenp]
	}

LeetCode