文章 217
评论 6
浏览 143928
String - 44. Wildcard Matching

String - 44. Wildcard Matching

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


标题:String - 44. Wildcard Matching
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2020/02/11/1581423604056.html

Nothing just happens, it's all part of a plan.

取消