Leetcode44-通配符匹配-Python实现

• 题目要求：

• 思路：

  • 两个字符串逐个匹配，会遇到三种情况
  • 情况1：字符相等，或字符模式p中的字符为"?"，那么可以比对下一位
  • 情况2：字符不等，但字符模式p中的字符为星号（*）

  • !

    • 这种情况下，用一个prestar来标记遇到星号的下标，prestar初始化为-1
    • 将字符模式p的指针移到下一个位置
    • 并将s指针的当前指向的下标保存下来，用来标记当前对比过了

  • 情况3：字符不等，但是prestar不为-1，也就是在这之前出现过星号

    • 那么把s字符串的指针移到之前对比过的下一个位置，再进行比对，把match也更改到下一个位置
  • 如果不为上述三种情况，也就是当前的两个字符不相同，之前也没有出现过星号，说明两个字符串真的不相同，返回False
• 核心代码：

i, j, prestar, match = 0, 0, -1, -1while 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)