LeetCode: Wildcard Matching

Posted on August 5, 2019July 26, 2020 by braindenny

Wildcard Matching

Similar Problems:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/wildcard-matching
// Basic Ideas: dynamic programming
//
//  dp(i, j): s[0:i], p[0:j]
//     if p[j] is neither '?' nor '*'
//     if p[j] is '?'
//     if p[j] is '*'
//          dp(i-1, j): treat as zero
//          dp(i, j-1): treat as multiple
//
// Notice: wildcard match is different from regexp match
// Complexity: Time O(n*m), Space O(n*m)
func isMatch(s string, p string) bool {
    dp := make([][]bool, len(s)+1)
    for i, _ := range dp {
        dp[i] = make([]bool, len(p)+1)
    }
    // init base condition
    dp[0][0] = true
    for j:=1; j<len(dp[0]); j++ {
        if dp[0][j-1] && p[j-1] == '*' {
            dp[0][j] = true
        }
    }
    // dp
    for i:=1; i<len(dp); i++ {
        for j:=1; j<len(dp[0]); j++ {
            if p[j-1] == '?' {
                if dp[i-1][j-1] {
                    dp[i][j] = true
                }
            } else {
                if p[j-1] != '*' {
                    if p[j-1] == s[i-1] {
                        dp[i][j] = dp[i-1][j-1]
                    }
                } else {
                    // treat * as empty
                    if dp[i][j-1] {
                        dp[i][j] = true
                    } else {
                        // treat * as any
                        if dp[i-1][j] {
                            dp[i][j] = true
                        }
                    }
                }
            }
        }
    }
    return dp[len(s)][len(p)]
}

Post Views: 0