String - 44. Wildcard Matching

44. Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

思路：

题目意思是实现一个模式串匹配，*可以代表任意个字符，?可以代表任意一个字符，让实现p串能否匹配s串。很难的一道题，如果没有做过，非常难想出最优解。做法就是使用四个指针，两个探索指针，两个标志位指针来遍历s串和p 串。

代码：

go：

func isMatch(s string, p string) bool {
    var (
        sp = 0  // s串的探索指针
        pp = 0  // p串的探索指针
        matchPos = 0  // 记录p串发现"*"时，s串的sp走到的位置
        star = -1   // 记录p串的“*”的位置
    )
    
    for sp < len(s) {
        // 如果p串和s串匹配，或者p串有“?”两个指针都往后移动
        if pp < len(p) && (s[sp] == p[pp] || p[pp] == '?') { 
            pp++
            sp++
        // 如果发现p串有“*”,则记录下“*”的位置以及s匹配到的位置，并且p串的探索指针往后移动
        } else if pp < len(p) && p[pp] == '*' {
            star = pp
            matchPos = sp
            pp++
        // 如果在p串已经发现有“*”，那么就把p串探索指针更新到“*”的后面，
        // 同时从发现“*”的时候的s串的探索指针sp往后移动，继续后面的匹配
        } else if star != -1 { // 发现p有*
            pp = star + 1
            sp = matchPos
            sp++
        // 否则就不能匹配，直接返回false
        } else {
            return false
        }
    }
    
    // 检查p串是否走完
    for pp < len(p) && p[pp] == '*' {
        pp++
    }
    
    return pp == len(p)
}