## String - 44. Wildcard Matching

Updated on with 0 views and 0 comments
1. 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:
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
``````

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)
}
``````