leeyupeng

leeyupeng@126.com

0%

leetcode.44.通配符匹配

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

通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

回溯法

思路分析

双指针 i，j

  • 1.若s[i]==p[j] 则i++,j++;
  • 2.若p[j]==’?’ 则i++,j++;
  • 3.若p[j]==’*’ 则j++，并更新star的位置和回溯时的起点
  • 4.若s[i]!=p[j] 则
    • 1.如果star位置的-1，匹配失败；
    • 2.回溯，起点加1，j回到起点 star+1;

执行用时 :12 ms, 在所有 C++ 提交中击败了86.14%的用户
内存消耗 :6.6 MB, 在所有 C++ 提交中击败了100.00%的用户

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
	bool isMatch(string s, string p) {
		int i = 0,j = 0,start = 0,star = -1;
		while (i < s.length()) {
			if (j < p.length() && (s[i] == p[j] || p[j] == '?')) { i++; j++; continue; }
			else if (j < p.length() && p[j] == '*') { start = i; star = j; j++; continue; }
			else if (star == -1) { return false; }
			else { start++; i = start; j = star + 1; continue; }
		}
		while (j < p.length() && p[j] == '*') { j++; }
		return j == p.length();
	}
};

动态规划

思路分析

dp[i][j] 代表 s[0:i-1] 是否 和 p[0:j-1] 匹配
情况:

  • 1.s[i] == p[j]
  • 2.p[j] == ‘*’
  • 3.p[j] == ‘?’

转移方程:

  • 1.dp[i][j] = dp[i-1][j-1]
  • 2.dp[i][j] = dp[i-1][j] || dp[i][j-1]
  • 3.dp[i][j] = dp[i-1][j-1]

执行用时 :248 ms, 在所有 C++ 提交中击败了23.38%的用户
内存消耗 :11.3 MB, 在所有 C++ 提交中击败了66.67%的用户

代码实现

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
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 > 0 && p[j - 1] == '*') {
				dp[0][j] = dp[0][j] || dp[0][j - 1];
			}
		}
		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] == '*') {
					dp[i][j] = dp[i - 1][j] || dp[i][j-1];
				}
			}
		}
		return dp[n][m];
	}
};

KMP算法

思路分析

在回溯法的基础上，回溯时根据公共前缀，只回溯j

  • 1.p[j]==’*’ next[j]=j,next[j+1]=j
  • 2.p[j]==’?’ next[j+1]=next[j]+1

代码实现(静态KMP算法)

next的时候，验证前缀中的？是否匹配

执行用时 :8 ms, 在所有 C++ 提交中击败了94.13%的用户
内存消耗 :7.1 MB, 在所有 C++ 提交中击败了100.00%的用户 

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class Solution {
public:
	void getnext(string& p, vector<int>& next) {
		int star = -1;
		int k = 0;
		next[0] = -1;
		if (p.length() > 0 && p[0] == '*') { next[0] = 0; }
		for (int j = 0; j < p.length(); j++)
		{
			if (p[j] == '*') {
				star = j;
				next[j] = j;
				next[j + 1] = j;
			}
			else if (star == -1) { next[j + 1] = -1; }
			else if (p[j] == '?') {
				next[j + 1] = next[j] + 1;
			}
			else {
				k = next[j];
				while (k >= 0) {
					if (p[k] == '*' || p[k] == '?' || p[j] == '?' || p[k] == p[j]) { break; }
					k = next[k];
				}
				next[j + 1] = k + 1;
			}
		}
	}

	int getnextk(string& s, string& p, vector<int>& next, int i, int j) {
		int k = j;
		int jj = 0;
		do {
			k = next[k];
			for (jj = k-1; jj >= 0; jj--) {
				if (p[jj] == '*') { break; }
				if (p[j - (k - jj)] == '?' && p[jj] != '?' && s[i - (k - jj)] != p[jj]){
					break;
				}
			}
			if (jj <= -1) { break; }
			if (p[jj] == '*') { break; }			

		} while (k >= 0 && p[k] != '*');
		return k;
	}
	bool isMatch(string s, string p) {
		int i = 0, j = 0, star = -1;
		int n = s.length();
		int m = p.length();
		int k;
		int jj;

		vector<int> next(m + 1);
		getnext(p, next);
		while (i < n) {
			if (j >= m) {
				j = getnextk(s,p,next,i,j);
				if (j == -1) { return false; }
				if (p[j] == '*') { i++; j++; }
				continue;
			}
			else if (s[i] == p[j]) {
				i++; j++;
				continue;
			}
			else if (p[j] == '?') {
				{
				}
				i++; j++;
				continue;
			}
			else if (p[j] == '*') {
				star = j;
				j++;
				continue;
			}
			else {
				j = getnextk(s, p, next, i, j);
				if (j == -1) { return false; }
				if (p[j] == '*') { i++; j++; }
				continue;
			}
		}
		while (j < p.length() && p[j] == '*') { j++; }
		return j == p.length();
	}
};

代码实现(动态KMP算法)

动态生成next，遇到*和？特殊处理

执行用时 :4 ms, 在所有 C++ 提交中击败了98.84%的用户
内存消耗 :7 MB, 在所有 C++ 提交中击败了100.00%的用户 

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
38
39
40
class Solution {
public:
	bool isMatch(string s, string p) {
		int i = 0, j = 0, star = -1;
		int nexttemp;
		int nextindex;
		vector<int> next(p.length() + 1);
		next[0] = -1;
		if (p.length() > 0 && p[0] == '*') { next[0] = 0; }
		while (i < s.length()) {
			if (j < p.length() && (s[i] == p[j] || p[j] == '?')) {
				if (star == -1) { next[j + 1] = -1; }
				else {
					nexttemp = next[j];
					while (nexttemp >= 0 && (p[nexttemp] != '*' && p[nexttemp] != '?' && p[nexttemp] != s[i])) {
						nexttemp = next[nexttemp];
					}
					next[j + 1] = nexttemp + 1;
				}
				i++; j++;
				continue;
			}
			else if (j < p.length() && p[j] == '*') {
				star = j;
				next[j] = j;
				next[j + 1] = j;
				j++;
				continue;
			}
			else {
				j = next[j];
				if (j == -1) { return false; }
				if (p[j] == '*') { i++; j++; }
				continue;
			}
		}
		while (j < p.length() && p[j] == '*') { j++; }
		return j == p.length();
	}
};

代码实现(优化)

执行用时 :4 ms, 在所有 C++ 提交中击败了98.82%的用户
内存消耗 :7.1 MB, 在所有 C++ 提交中击败了100.00%的用户 

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class Solution {
public:
	void getnext(string& p, vector<int>& next) {
		int star = -1;
		int k = 0;
		next[0] = -1;
		if (p.length() > 0 && p[0] == '*') { next[0] = 0; }
		for (int j = 0; j < p.length(); j++)
		{
			if (p[j] == '*') {
				star = j;
				next[j] = j;
				next[j + 1] = j;
			}
			else if (star == -1) { next[j + 1] = -1; }
			else if (p[j] == '?') {
				next[j + 1] = next[j] + 1;
			}
			else {
				k = next[j];
				while (k >= 0) {
					if (p[k] == '*' || p[k] == '?' || p[j] == '?' || p[k] == p[j]) { break; }
					k = next[k];
				}
				next[j + 1] = k + 1;
			}
		}
	}
	void refreshnext(string& p, vector<int>& next, int star, int j, char c) {
		int k = 0;
		k = next[j];
		while (k >= 0) {
			if (p[k] == '*' || p[k] == '?' || p[k] == c) { break; }
			k = next[k];
		}
		if (next[j + 1] == k + 1) { return; }
		next[j + 1] = k + 1;

		for (int jj = j + 1; jj < p.length(); jj++)
		{
			if (p[jj] == '*') {
				break;
			}
			else if (star == -1) { next[jj + 1] = -1; }
			else if (p[jj] == '?') {
				next[jj + 1] = next[jj] + 1;
			}
			else {
				k = next[jj];
				while (k >= 0) {
					if (p[k] == '*' || p[k] == '?' || p[jj] == '?' || p[k] == p[jj]) { break; }
					k = next[k];
				}
				next[jj + 1] = k + 1;
			}
		}
	}

	bool isMatch(string s, string p) {
		int i = 0, j = 0, star = -1;
		int n = s.length();
		int m = p.length();
		int k;
		int jj;

		vector<int> next(m + 1);
		getnext(p, next);
		while (i < n) {
			if (j >= m) {
				j = next[j];
				if (j == -1) { return false; }
				if (p[j] == '*') { i++; j++; }
				continue;
			}
			else if (s[i] == p[j]) {
				i++; j++;
				continue;
			}
			else if (p[j] == '?') {
				if (star != -1) { refreshnext(p, next, star, j, s[i]); }
				i++; j++;
				continue;
			}
			else if (p[j] == '*') {
				star = j;
				j++;
				continue;
			}
			else {
				j = next[j];
				if (j == -1) { return false; }
				if (p[j] == '*') { i++; j++; }
				continue;
			}
		}
		while (j < p.length() && p[j] == '*') { j++; }
		return j == p.length();
	}
};

BM算法

思路分析

代码实现

1
2


FA有限状态自动机

思路分析

代码实现

1
2


NFA

思路分析

代码实现

1
2


DFA

思路分析

代码实现

1
2