leetcode10：正则表达式匹配

题目链接

leetcode

题目描述

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

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

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

C++ 代码

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <cstring>
using namespace std;

/*
    暴力解法：递归尝试所有可能的匹配路径，直到找到一个匹配为止。

    递归函数：
        递归函数 matchHelper(s, p, i, j)，其中 i 和 j 分别表示字符串 s 和模式 p 的当前索引。
        如果模式 p 已经匹配完（j == p.size()），检查字符串 s 是否也匹配完（i == s.size()）。
    处理 *：如果模式的下一个字符是 *（即 p[j + 1] == '*'），有两种情况：
        * 匹配零次前面的字符：递归调用 matchHelper(s, p, i, j + 2)。
        * 匹配多次前面的字符：尝试匹配多个字符，直到不匹配为止。
    普通字符匹配：
        如果当前字符匹配（s[i] == p[j] 或 p[j] == '.'），
        递归调用 matchHelper(s, p, i + 1, j + 1)。
    返回结果：
        如果所有路径都尝试过，返回最终结果。

    时间复杂度：O(2^(m+n))
        其中 m 是字符串 s 的长度，n 是模式 p 的长度。
        暴力解法的时间复杂度是指数级的 O(2^(m+n))，
        每个字符的匹配可能有两种选择（匹配或不匹配），而 * 的存在进一步增加了分支数量。
    空间复杂度：
        由于递归调用栈的深度，空间复杂度为 O(m+n)。
        在最坏情况下，递归调用栈的深度可能达到字符串和模式串的总长度。
*/
class Solution_0 {
public:
    bool isMatch(string s, string p) {
        // 指针 i，j 从索引 0 开始移动
        return matchHelper(s, p, 0, 0);
    }

    bool matchHelper(string& s, string& p, int i, int j) {
        // 如果模式串 p 已经匹配完，则检查字符串 s 是否匹配完
        if (j == p.size()) {
            return i == s.size();
        }
        // 如果模式串 p 的下一个字符是 '*'
        if (j + 1 < p.size() && p[j + 1] == '*') {
            // '*' 匹配零次前面的字符
            if (matchHelper(s, p, i, j + 2)) {
                return true;
            }

            // '*' 匹配多次前面的字符
            while (i < s.size() && (s[i] == p[j] || p[j] == '.')) {
                if (matchHelper(s, p, i + 1, j + 2)) {
                    return true;
                }
                i ++;
            }
            return false;
        }
        // 普通字符匹配
        if (i < s.size() && (s[i] == p[j] || p[j] == '.')) {
            return matchHelper(s, p, i + 1, j + 1);
        }

        return false;
    }
};

/*
    递归实现 + 备忘录优化

    时间复杂度：O(mn)
        时间复杂度为 O(mn)，其中 m 是字符串 s 的长度，n 是模式 p 的长度。
    空间复杂度：O(mn)
        空间复杂度为 O(mn)，存储子问题的结果。
*/
class Solution_1 {
public:
    bool isMatch(string s, string p) {
        // 使用 unordered_map 作为备忘录，存储已经计算过的子问题结果
        unordered_map<string, bool> memo;
        // 指针 i，j 从索引 0 开始移动
        return matchHelper(s, p, 0, 0, memo);
    }

    bool matchHelper(string& s, string& p, int i, int j, unordered_map<string, bool>& memo) {
        // 构造备忘录的键
        string key = to_string(i) + "," + to_string(j);
	    // 如果已经计算过，则返回结果
        if (memo.find(key) != memo.end()) {
            return memo[key];
        }

	    // 如果模式串 p 已经匹配完，则检查字符串 s 是否匹配完
        if (j == p.size()) {
            memo[key] = (i == s.size());
            return memo[key];
        }
	    // 如果模式串 p 的下一个字符是 '*'
        if (j + 1 < p.size() && p[j + 1] == '*') {
            // '*' 匹配零次前面的字符
            if (matchHelper(s, p, i, j + 2, memo)) {
                memo[key] = true;
                return true;
            }

            // '*' 匹配多次前面的字符
            while (i < s.size() && (s[i] == p[j] || p[j] == '.')) {
                if (matchHelper(s, p, i + 1, j + 2, memo)) {
                    memo[key] = true;
                    return true;
                }
                i ++;
            }
        } else {
            // 普通字符匹配
            if (i < s.size() && (s[i] == p[j] || p[j] == '.')) {
                if (matchHelper(s, p, i + 1, j + 1, memo)) {
                    memo[key] = true;
                    return true;
                }
            }
        }

        // 如果所有路径都尝试过，返回 false
        memo[key] = false;
        return false;
    }
};

/*
    状态表示：
        f[i][j]表示 s[1...i] 和 p[1...j] 是否匹配
    状态计算：
        p[j] != '*'
            f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.')
        p[j] == '*',
            f[i][j] = f[i][j - 2] || f[i - 1][j] && (s[i] == p[j] || p[j] == '.')
            匹配零个字符 
                f[i][j] = f[i][j − 2]
            匹配一个或多个字符
                f[i][j] = f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.')

    时间复杂度：O(mn)
        m 表示 s 的长度，n 表示 p 的长度，总共 mn 个状态，
        状态转移复杂度 O(1)，所以时间复杂度是 O(mn)。
    空间复杂度：O(mn)
        使用了一个大小为 (m+1)*(n+1) 的二维数组 dp，空间复杂度为 O(mn)。
*/
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        s = ' ' + s, p = ' ' + p;
        vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
        // 初始化，空字符串与空模式串匹配
        f[0][0] = true;
        // 初始化，处理模式串中的匹配符 '*'
        for (int j = 2; j <= n; j ++) {
            if (p[j] == '*') {
                f[0][j] = f[0][j - 2];
            }
        }
        // 状态计算
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (p[j] != '*') {
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                } else if (p[j] == '*') {
                    f[i][j] = f[i][j - 2] || f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
                }
            }
        }

        return f[m][n];
    }
};

/*
    思路同上
*/
class Solution_3 {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        s = ' ' + s, p = ' ' + p;
        vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
        // 初始化，空字符串与空模式串匹配
        f[0][0] = true;
        // 处理模式串中的匹配符 '*'
        for (int j = 2; j <= n; j ++) {
            if (p[j] == '*') {
                f[0][j] = f[0][j - 2];
            }
        }
        // 状态计算
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (p[j] != '*') {
                    f[i][j] = f[i - 1][j - 1] && match(s[i], p[j]);
                } else if(p[j] == '*') {
                    f[i][j] = f[i][j - 2] || f[i - 1][j] && match(s[i], p[j - 1]);
                }
            }
        }

        return f[m][n];
    }

    bool match(char s, char p) {
        return s == p || p == '.';
    }
};

int main() {
    Solution solution;
    vector<string> s_cases = { "aa", "aa", "ab" };
    vector<string> p_cases = { "a", "a*", ".*" };

    for (int i = 0; i < s_cases.size(); i ++) {
        cout << "Input: s = " << s_cases[i] << ", p = " << p_cases[i] << endl;
        cout << "Output: " << (solution.isMatch(s_cases[i], p_cases[i]) ? "true" : "false") << endl;
    }

    return 0;
}

Golang 代码

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
package main

import (
	"fmt"
	"strconv"
)

/*
	递归实现

	时间复杂度：O(2^(m+n))
       其中 m 是字符串 s 的长度，n 是模式 p 的长度。
	   最坏情况下为 O(2^(m+n))，实际运行时间可能因剪枝而降低。
	空间复杂度：O(m+n)
		由递归调用栈占用。
*/
func isMatch_0(s string, p string) bool {
	return dfs_0(s, p, 0, 0)
}

func dfs_0(s, p string, i, j int) bool {
	// 如果模式串 p 已经匹配完，则检查字符串 s 是否匹配完
	if j == len(p) {
		return i == len(s)
	}
	// 如果模式串 p 的下一个字符是 '*'
	if j+1 < len(p) && p[j+1] == '*' {
		// '*' 匹配零次前面的字符
		if dfs_0(s, p, i, j+2) {
			return true
		}
		// '*' 匹配多次前面的字符
		for i < len(s) && (s[i] == p[j] || p[j] == '.') {
			if dfs_0(s, p, i+1, j+2) {
				return true
			}
			i++
		}
	} else {
		// 普通字符匹配
		if i < len(s) && (s[i] == p[j] || p[j] == '.') {
			if dfs_0(s, p, i+1, j+1) {
				return true
			}
		} 
	}

	return false
}

/*
   递归实现 + 备忘录优化

   时间复杂度：O(mn)
       时间复杂度为 O(mn)，其中 m 是字符串 s 的长度，n 是模式 p 的长度。
   空间复杂度：O(mn)
       空间复杂度为 O(mn)，存储子问题的结果。
*/
func isMatch_1(s string, p string) bool {
	memo := make(map[string]bool)
	return dfs(s, p, 0, 0, memo)
}

func dfs(s, p string, i, j int, memo map[string]bool) bool {
	// 构造备忘录的键
	key := strconv.Itoa(i) + "," + strconv.Itoa(j)
	// 如果已经计算过，则返回结果
	if val, ok := memo[key]; ok {
		return val
	}

	// 如果模式串 p 已经匹配完，则检查字符串 s 是否匹配完
	if j == len(p) {
		memo[key] = (i == len(s))
		return memo[key]
	}
	// 如果模式串 p 的下一个字符是 '*'
	if j+1 < len(p) && p[j+1] == '*' {
		// '*' 匹配零次前面的字符
		if dfs(s, p, i, j+2, memo) {
			memo[key] = true
			return true
		}
		// '*' 匹配多次前面的字符
		for i < len(s) && (s[i] == p[j] || p[j] == '.') {
			if dfs(s, p, i+1, j+2, memo) {
				memo[key] = true
				return true
			}
			i++
		}
	} else {
		// 普通字符匹配
		if i < len(s) && (s[i] == p[j] || p[j] == '.') {
			if dfs(s, p, i+1, j+1, memo) {
				memo[key] = true
				return true
			}
		}
	}

	// 如果所有路径都试过，则返回 false
	memo[key] = false
	return false
}

/*
   动态规划：
       使用二维数组 dp[i][j] 表示字符串 s[:i] 是否与正则表达式 p[:j] 匹配。
       初始化dp[0][0] = true，因为空字符串与空正则表达式匹配。
       初始化正则表达式中的 * 情况，dp[0][j] = dp[0][j-2]，表示 * 匹配 0 次前面的元素。
   动态规划状态转移方程：
		如果 p[j-1] 是 . 或与 s[i-1] 匹配，
			则 dp[i][j] = dp[i-1][j-1]。
		如果 p[j-1] 是 *，
			dp[i][j] = dp[i][j-2]，表示 * 匹配 0 次前面的元素。
		如果 p[j-2] 是 . 或与 s[i-1] 匹配，
			则 dp[i][j] = dp[i][j] || dp[i-1][j]，表示 * 匹配 1 次或多次前面的元素。

    时间复杂度：O(mn)
        遍历两个字符串的每个字符，时间复杂度为 O(mn)，
		其中 m 和 n 分别是字符串和正则表达式的长度。
    空间复杂度：O(mn)
        使用了一个大小为 (m+1)*(n+1) 的二维数组 dp，空间复杂度为 O(mn)。
*/
// isMatch 判断字符串 s 是否与正则表达式 p 匹配
func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    dp := make([][]bool, m+1)
    for i := range dp {
        dp[i] = make([]bool, n+1)
    }
    // 初始化，空字符串与空模式串匹配
    dp[0][0] = true
	// 初始化，模式串 p 的前缀匹配空字符串的情况
    for j := 2; j <= n; j += 2 {
        if p[j-1] == '*' {
            dp[0][j] = dp[0][j-2]
        }
    }

    // 状态计算
    for i := 1;  i <= m; i ++ {
        for j := 1; j <= n; j ++ {
            // 普通字符匹配一次
            if p[j-1] == '.' || p[j-1] == s[i-1] {
                dp[i][j] = dp[i-1][j-1]
            } else if p[j-1] == '*' {
                // '*' 匹配 0 次前面的元素
                dp[i][j] = dp[i][j-2]
                // '*' 匹配 1 次或多次前面的元素
                if p[j-2] == '.' || p[j-2] == s[i-1] {
                    dp[i][j] = dp[i][j] || dp[i-1][j]
                }
            }
        }
    }

    return dp[m][n]
}

func main() {
	// 测试用例
	testCases := []struct {	
		s        string
		p        string
		expected bool
	}{
		{
			s:        "aa",
			p:        "a",
			expected: false,
		},
		{
			s:        "aa",
			p:        "a*",
			expected: true,
		},
		{
			s:        "ab",
			p:        ".*",
			expected: true,
		},
	}

	for i, tc := range testCases {
		result := isMatch(tc.s, tc.p)
		fmt.Printf("Test Case %d, Input: s = %q, p = %q\n", i+1, tc.s, tc.p)

		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}
#leetcode
leetcode10：正则表达式匹配
https://lcf163.github.io/2023/08/17/leetcode10：正则表达式匹配/
作者
乘风的小站
发布于
2023年8月17日
许可协议