Leetcode44-通配符匹配-Python实现

42次阅读

共计 942 个字符，预计需要花费 3 分钟才能阅读完成。

题目要求：

思路：
- 两个字符串逐个匹配，会遇到三种情况
- 情况 1：字符相等，或字符模式 p 中的字符为 ”?”，那么可以比对下一位
- 情况 2：字符不等，但字符模式 p 中的字符为星号（*）
- !
  - 这种情况下，用一个 prestar 来标记遇到星号的下标，prestar 初始化为 -1
  - 将字符模式 p 的指针移到下一个位置
  - 并将 s 指针的当前指向的下标保存下来，用来标记当前对比过了
- 情况 3：字符不等，但是 prestar 不为 -1，也就是在这之前出现过星号
  - 那么把 s 字符串的指针移到之前对比过的下一个位置，再进行比对，把 match 也更改到下一个位置
- 如果不为上述三种情况，也就是当前的两个字符不相同，之前也没有出现过星号，说明两个字符串真的不相同，返回 False
核心代码：

i, j, prestar, match = 0, 0, -1, -1
while i < len(pre):
    if j < len(cur) and (pre[i] == cur[j] or cur[j] == "?" ):
        i += 1
        j += 1
    elif j < len(cur) and cur[j] == "*":
        prestar = j
        j += 1
        match = i
    elif prestar != -1:
        j = prestar + 1
        i = match + 1
        match = i
    else:
        return False

完整代码：

class Solution:
    def isMatch(self, pre: str, cur: str) -> bool:
        i, j, prestar, match = 0, 0, -1, -1
        while i < len(pre):
            if j < len(cur) and (pre[i] == cur[j] or cur[j] == "?" ):
                i += 1
                j += 1
            elif j < len(cur) and cur[j] == "*":
                prestar = j
                j += 1
                match = i
            elif prestar != -1:
                j = prestar + 1
                i = match + 1
                match = i
            else:
                return False
        # 上一段代码只跟踪了字符串 s，也就是 pre，如果字符模式 p 字符串后面还有字符，如果后面的字符是 *，那么可以继续看下一个字符
        while j < len(cur) and cur[j] == "*":
            j += 1
        # 如果当前位置不为字符串 p 的长度，说明做字符串 p 的 * 后面（如果有），还有未匹配的字符，说明两个字符串不完全匹配
        return j == len(cur)

正文完