leeyupeng

leeyupeng@126.com

0%

leetcode.10.正则表达式匹配

发表于 更新于 分类于 ， 阅读次数： Valine：

正则表达式匹配

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

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

动态规划

思路分析

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
	bool isMatch(string s, string p) {
		int n = s.length();
		int m = p.length();
		vector<vector<bool>> dp(n + 1);
		for (int i = 0; i < n + 1; i++) {
			dp[i].insert(dp[i].begin(),m + 1,false);
		}

		dp[0][0] = true;

		for (int j = 0; j < m + 1; j++) {
			if (j > 1 && p[j-1] == '*') {
				dp[0][j] = dp[0][j] || dp[0][j - 2];
			}
		}
		for (int i = 1; i < n + 1; i++) {
			for (int j = 1; j < m + 1; j++) {
				if (s[i-1] == p[j-1]) {
					dp[i][j] = dp[i-1][j-1];
				}
				else if (p[j-1] == '.') {
					dp[i][j] = dp[i-1][j-1];
				}
				else if (p[j-1] == '*') {
					if (j > 1) { dp[i][j] = dp[i][j] || dp[i][j - 2]; }
					if (j > 1 && (s[i-1] == p[j - 2] || p[j - 2] == '.')) {
						dp[i][j] = dp[i][j] || dp[i-1][j-1];
						dp[i][j] = dp[i][j] || dp[i-1][j];
					}
				}
			}
		}
		return dp[n][m];
	}
};