Joyce' Blog
0%

Regular Expression

发表于 更新于

题目描述

给定一个字符串 s 和一个字符规律 p，实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

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

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regular-expression-matching

解题思路

使用==动态规划==的方法。如果s[0..i) 成功匹配 p[0..j) ，令dp[i][j]为true，否则为false。”.”的情况较易处理，主要需要考虑”*“的影响，它可能表示多个连续相同的字母，也可能使它的前一个字母“消失”。一、p[j - 1] != ‘*‘，这是最简单的情况，只需要直接比较当前的两个字母，并向前移动 i 和 j ；二、p[j - 1] == ‘*‘，根据前面分析的’*‘的两种作用，这里需要细分为两种情况。在所有的情况下，i 和 j 都在单个或一起向前移，所以需要一个二重循环，在最内层用 if - else 对dp进行赋值。注意dp[0][0] = 1，表示s和p都为空串；dp[0][j]=0，表示s串前推到头时，如果p串还未结束，则返回false。

状态转移方程：

  1. dp[i][j] = dp[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
  2. dp[i][j] = dp[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 time;
  3. dp[i][j] = dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 time.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool isMatch(string s,string p)
{
	int m = s.length(), n = p.length();
	bool **dp = new bool*[m+1];
	for (int i = 0; i < m + 1; ++i)	
		dp[i] = new bool[n + 1];
	for (int i = 0; i <= m; ++i)
		for (int j = 0; j <= n; ++j)
			dp[i][j] = 0;
	dp[0][0] = 1;
	for (int i = 0; i <= m; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (p[j - 1] == '*')
				dp[i][j] = dp[i][j - 2] || (i>0&&dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
			else
				dp[i][j] = i>0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
		}
	}
	return dp[m][n];
}

报错解决

报错：string subscript out of range

解决：可能的原因是数组索引超出范围。在此次代码中出现这个问题的原因是我把 j 写成 i 了，导致访问数组是下标超限。