算法leetcode｜44. 通配符匹配（rust重拳出击）-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法leetcode｜44. 通配符匹配（rust重拳出击）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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/ 博客原创~文章来源地址https://www.toymoban.com/news/detail-407247.html

到了这里，关于算法leetcode｜44. 通配符匹配（rust重拳出击）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！