【算法】10. 正则表达式匹配(多语言实现)
【摘要】 给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 . 和 * 的正则表达式匹配。
. 匹配任意单个字符
* 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
10. 正则表达式匹配:
给你一个字符串 s
和一个字符规律 p
,请你来实现一个支持 .
和 *
的正则表达式匹配。
.
匹配任意单个字符*
匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s
的,而不是部分字符串。
样例 1:
输入:
s = "aa", p = "a"
输出:
false
解释:
"a" 无法匹配 "aa" 整个字符串。
样例 2:
输入:
s = "aa", p = "a*"
输出:
true
解释:
因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。
样例 3:
输入:
s = "ab", p = ".*"
输出:
true
解释:
".*" 表示可匹配零个或多个('*')任意字符('.')。
提示:
1 <= s.length <= 20
1 <= p.length <= 30
s
只包含从a-z
的小写字母。p
只包含从a-z
的小写字母,以及字符.
和*
。- 保证每次出现字符
*
时,前面都匹配到有效的字符
分析
- 面对这道算法题目,二当家的陷入了沉思。
- 如果从整个字符串去考虑,会有些迷茫。
- 用动态规划的思想,可以从0个字符到1个字符,再到2个字符,整个字符串的匹配情况依赖于去掉最后一个字符的匹配情况,以此类推。
题解
rust
impl Solution {
pub fn is_match(s: String, p: String) -> bool {
let s = s.as_bytes();
let p = p.as_bytes();
let match_c = |i, j| -> bool {
i != 0 && (p[j - 1] == '.' as u8 || s[i - 1] == p[j - 1])
};
let mut dp = vec![vec![false; p.len() + 1]; s.len() + 1];
dp[0][0] = true;
(0..=s.len()).for_each(|i| {
(1..=p.len()).for_each(|j| {
dp[i][j] = if p[j - 1] == '*' as u8 {
match_c(i, j - 1) && dp[i - 1][j] || dp[i][j - 2]
} else {
match_c(i, j) && dp[i - 1][j - 1]
};
})
});
dp[s.len()][p.len()]
}
}
go
func isMatch(s string, p string) bool {
m, n := len(s), len(p)
matches := func(i, j int) bool {
if i == 0 {
return false
}
if p[j-1] == '.' {
return true
}
return s[i-1] == p[j-1]
}
f := make([][]bool, m+1)
for i := 0; i < len(f); i++ {
f[i] = make([]bool, n+1)
}
f[0][0] = true
for i := 0; i <= m; i++ {
for j := 1; j <= n; j++ {
if p[j-1] == '*' {
f[i][j] = f[i][j] || f[i][j-2]
if matches(i, j-1) {
f[i][j] = f[i][j] || f[i-1][j]
}
} else if matches(i, j) {
f[i][j] = f[i][j] || f[i-1][j-1]
}
}
}
return f[m][n]
}
c++
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
auto matches = [&](int i, int j) {
if (i == 0) {
return false;
}
if (p[j - 1] == '.') {
return true;
}
return s[i - 1] == p[j - 1];
};
vector<vector<int>> f(m + 1, vector<int>(n + 1));
f[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
f[i][j] |= f[i][j - 2];
if (matches(i, j - 1)) {
f[i][j] |= f[i - 1][j];
}
} else {
if (matches(i, j)) {
f[i][j] |= f[i - 1][j - 1];
}
}
}
}
return f[m][n];
}
};
java
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
char pc = p.charAt(j - 1);
if (pc == '*') {
dp[i][j] = dp[i][j - 2]; // *匹配0次
if (i > 0 && !dp[i][j]) {
char prePc = p.charAt(j - 2);
if (prePc == '.'
|| s.charAt(i - 1) == prePc) {
dp[i][j] = dp[i - 1][j]; // *匹配1次或多次
}
}
} else if (i > 0 && (pc == '.' || s.charAt(i - 1) == pc)) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
}
typescript
function isMatch(s: string, p: string): boolean {
let m = s.length;
let n = p.length;
const matches = function (i: number, j: number): boolean {
if (i == 0) {
return false;
}
if (p[j - 1] == '.') {
return true;
}
return s[i - 1] == p[j - 1];
};
let f = Array.from({ length: m + 1 }, () => Array.from({ length: n + 1 }, () => false));
f[0][0] = true;
for (let i = 0; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
f[i][j] = f[i][j] || f[i][j - 2];
if (matches(i, j - 1)) {
f[i][j] = f[i][j] || f[i - 1][j];
}
} else if (matches(i, j)) {
f[i][j] = f[i][j] || f[i - 1][j - 1];
}
}
}
return f[m][n];
};
python
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
def matches(i: int, j: int) -> bool:
if i == 0:
return False
if p[j - 1] == '.':
return True
return s[i - 1] == p[j - 1]
f = [[False] * (n + 1) for _ in range(m + 1)]
f[0][0] = True
for i in range(m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
f[i][j] |= f[i][j - 2]
if matches(i, j - 1):
f[i][j] |= f[i - 1][j]
else:
if matches(i, j):
f[i][j] |= f[i - 1][j - 1]
return f[m][n]
非常感谢你阅读本文~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://bbs.huaweicloud.cn/community/usersnew/id_1628396583336561 博客原创~
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)