文章目录
44. 通配符匹配：样例 1：样例 2：样例 3：样例 4：样例 5：
分析：题解：rustgoc++cpythonjava
44. 通配符匹配：
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
样例 1：
输入:
s = "aa"
p = "a"
输出:
false
解释:
"a" 无法匹配 "aa" 整个字符串。
样例 2：
输入:
s = "aa"
p = "*"
输出:
true
解释:
'*' 可以匹配任意字符串。
样例 3：
输入:
s = "cb"
p = "?a"
输出:
false
解释:
'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
样例 4：
输入:
s = "adceb"
p = "*a*b"
输出:
true
解释:
第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
样例 5：
输入:
s = "acdcb"
p = "a*c?b"
输出:
false
分析：
面对这道算法题目，二当家的再次陷入了沉思。字符本身的匹配很简单，但是还包含问好和星号。主要是星号匹配的处理，整体去看，比较迷茫，必须要分解问题，可以考虑使用动态规划。在模式字符串中出现的字符和问号可以理解为是固定匹配的，需要匹配的字符个数是固定的，都是需要匹配一个字符，而星号则需要暴力尝试，所以我们可以考虑把模式串按照星号分割，然后贪心的去尝试匹配字符和问号。当模式串中是字符或者问号，就在字符串中找和模式串能匹配的字符或者问号，如果查到底都无法完全匹配就说明不匹配，如果可以匹配，一直匹配到模式串的星号，则开始下一个子串的匹配。在匹配每个星号之间的子串时，使用了最普通的暴力匹配方式，没做什么优化，没使用什么技巧，事实上根据具体情况还有很多算法可以提高单纯匹配字符串的效率，可以了解 KMP 算法，字典树，AC自动机 等等，但是有点过于复杂了，一道题要搞多复杂啊，够了够了。除了使用贪心的算法，也可以使用动态规划，感觉动态规划更好理解一些。
题解：
rust
impl Solution {
pub fn is_match(s: String, p: String) -> bool {
fn is_all_stars(bs: &[u8], left: usize, right: usize) -> bool {
for i in left..right {
if bs[i] != b'*' {
return false;
}
}
return true;
}
fn is_char_match(u: u8, v: u8) -> bool {
u == v || v == b'?'
}
let sbs = s.as_bytes();
let pbs = p.as_bytes();
let (mut s_right, mut p_right) = (s.len(), p.len());
while s_right > 0 && p_right > 0 && pbs[p_right - 1] != b'*' {
if is_char_match(sbs[s_right - 1], pbs[p_right - 1]) {
s_right -= 1;
p_right -= 1;
} else {
return false;
}
}
if p_right == 0 {
return s_right == 0;
}
let (mut s_index, mut p_index) = (0, 0);
let (mut s_record, mut p_record) = (-1i32, -1i32);
while s_index < s_right && p_index < p_right {
if pbs[p_index] == b'*' {
p_index += 1;
s_record = s_index as i32;
p_record = p_index as i32;
} else if is_char_match(sbs[s_index], pbs[p_index]) {
s_index += 1;
p_index += 1;
} else if s_record != -1 && s_record + 1 < s_right as i32 {
s_record += 1;
s_index = s_record as usize;
p_index = p_record as usize;
} else {
return false;
}
}
return is_all_stars(pbs, p_index, p_right);
}
}
go
func isMatch(s string, p string) bool {
charMatch := func(u, v byte) bool {
return u == v || v == '?'
}
allStars := func(str string, left, right int) bool {
for i := left; i < right; i++ {
if str[i] != '*' {
return false
}
}
return true
}
for len(s) > 0 && len(p) > 0 && p[len(p)-1] != '*' {
if charMatch(s[len(s)-1], p[len(p)-1]) {
s = s[:len(s)-1]
p = p[:len(p)-1]
} else {
return false
}
}
if len(p) == 0 {
return len(s) == 0
}
sIndex, pIndex := 0, 0
sRecord, pRecord := -1, -1
for sIndex < len(s) && pRecord < len(p) {
if p[pIndex] == '*' {
pIndex++
sRecord, pRecord = sIndex, pIndex
} else if charMatch(s[sIndex], p[pIndex]) {
sIndex++
pIndex++
} else if sRecord != -1 && sRecord+1 < len(s) {
sRecord++
sIndex, pIndex = sRecord, pRecord
} else {
return false
}
}
return allStars(p, pIndex, len(p))
}
c++
class Solution {
public:
bool isMatch(string s, string p) {
auto allStars = [](const string &str, int left, int right) {
for (int i = left; i < right; ++i) {
if (str[i] != '*') {
return false;
}
}
return true;
};
auto charMatch = [](char u, char v) {
return u == v || v == '?';
};
while (s.size() && p.size() && p.back() != '*') {
if (charMatch(s.back(), p.back())) {
s.pop_back();
p.pop_back();
} else {
return false;
}
}
if (p.empty()) {
return s.empty();
}
int sIndex = 0, pIndex = 0;
int sRecord = -1, pRecord = -1;
while (sIndex < s.size() && pIndex < p.size()) {
if (p[pIndex] == '*') {
++pIndex;
sRecord = sIndex;
pRecord = pIndex;
} else if (charMatch(s[sIndex], p[pIndex])) {
++sIndex;
++pIndex;
} else if (sRecord != -1 && sRecord + 1 < s.size()) {
++sRecord;
sIndex = sRecord;
pIndex = pRecord;
} else {
return false;
}
}
return allStars(p, pIndex, p.size());
}
};
c
bool allStars(char *str, int left, int right) {
for (int i = left; i < right; ++i) {
if (str[i] != '*') {
return false;
}
}
return true;
}
bool charMatch(char u, char v) { return u == v || v == '?'; };
bool isMatch(char *s, char *p) {
int len_s = strlen(s), len_p = strlen(p);
while (len_s && len_p && p[len_p - 1] != '*') {
if (charMatch(s[len_s - 1], p[len_p - 1])) {
len_s--;
len_p--;
} else {
return false;
}
}
if (len_p == 0) {
return len_s == 0;
}
int sIndex = 0, pIndex = 0;
int sRecord = -1, pRecord = -1;
while (sIndex < len_s && pIndex < len_p) {
if (p[pIndex] == '*') {
++pIndex;
sRecord = sIndex;
pRecord = pIndex;
} else if (charMatch(s[sIndex], p[pIndex])) {
++sIndex;
++pIndex;
} else if (sRecord != -1 && sRecord + 1 < len_s) {
++sRecord;
sIndex = sRecord;
pIndex = pRecord;
} else {
return false;
}
}
return allStars(p, pIndex, len_p);
}
python
class Solution:
def isMatch(self, s: str, p: str) -> bool:
def is_all_stars(st: str, left: int, right: int) -> bool:
return all(st[i] == '*' for i in range(left, right))
def is_char_match(u: str, v: str) -> bool:
return u == v or v == '?'
s_right, p_right = len(s), len(p)
while s_right > 0 and p_right > 0 and p[p_right - 1] != '*':
if is_char_match(s[s_right - 1], p[p_right - 1]):
s_right -= 1
p_right -= 1
else:
return False
if p_right == 0:
return s_right == 0
s_index, p_index = 0, 0
s_record, p_record = -1, -1
while s_index < s_right and p_index < p_right:
if p[p_index] == '*':
p_index += 1
s_record, p_record = s_index, p_index
elif is_char_match(s[s_index], p[p_index]):
s_index += 1
p_index += 1
elif s_record != -1 and s_record + 1 < s_right:
s_record += 1
s_index, p_index = s_record, p_record
else:
return False
return is_all_stars(p, p_index, p_right)
java
class Solution {
public boolean isMatch(String s, String p) {
int sRight = s.length(), pRight = p.length();
while (sRight > 0 && pRight > 0 && p.charAt(pRight - 1) != '*') {
if (charMatch(s.charAt(sRight - 1), p.charAt(pRight - 1))) {
--sRight;
--pRight;
} else {
return false;
}
}
if (pRight == 0) {
return sRight == 0;
}
int sIndex = 0, pIndex = 0;
int sRecord = -1, pRecord = -1;
while (sIndex < sRight && pIndex < pRight) {
if (p.charAt(pIndex) == '*') {
++pIndex;
sRecord = sIndex;
pRecord = pIndex;
} else if (charMatch(s.charAt(sIndex), p.charAt(pIndex))) {
++sIndex;
++pIndex;
} else if (sRecord != -1 && sRecord + 1 < sRight) {
++sRecord;
sIndex = sRecord;
pIndex = pRecord;
} else {
return false;
}
}
return allStars(p, pIndex, pRight);
}
public boolean allStars(String str, int left, int right) {
for (int i = left; i < right; ++i) {
if (str.charAt(i) != '*') {
return false;
}
}
return true;
}
public boolean charMatch(char u, char v) {
return u == v || v == '?';
}
}
非常感谢你阅读本文~ 欢迎【点赞】【收藏】【评论】~ 放弃不难，但坚持一定很酷~ 希望我们大家都能每天进步一点点~ 本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~
好文链接
您阅读本篇文章共花了：
发表评论