LeetCode //C - 44. Wildcard Matching

44. Wildcard Matching

Given an input string (s) and a pattern ( p), implement wildcard pattern matching with support for ‘?’ and ‘*’ where:

• ‘?’ Matches any single character.
• ‘*’ Matches any sequence of characters (including the empty sequence).

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

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’.

Constraints:

• 0 <= s.length, p.length <= 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, ‘?’ or ‘*’.

From: LeetCode
Link: 44. Wildcard Matching

Solution:

Ideas:

Dynamic Programming Table (dp Array)
The function uses a 2D boolean array dp where dp[i][j] indicates whether the first i characters of the string s can be matched with the first j characters of the pattern p. The sizes of the dimensions are sLen+1 and pLen+1 to accommodate strings from length 0 (empty string) to their respective lengths.

Initialization

• dp[0][0]: An empty string always matches an empty pattern, so this is initialized to true.
• dp[0][j]: If the pattern is not empty but the string is, dp[0][j] can only be true if the pattern consists solely of the * character, which can match an empty sequence. This initialization propagates the true value rightward for all positions in the pattern that continue to have *.

Filling the dp Table
For each character in s (index i) and each character in p (index j), the function determines dp[i][j] based on the current characters of s and p:

• If p[j-1] is ‘*’: The * character can match zero or more characters. Therefore, dp[i][j] is true if:
  • dp[i][j-1] is true (the * matches zero characters, i.e., it acts as if it’s not there).
  • dp[i-1][j] is true (the * matches the current character of s plus any preceding sequence).
• If p[j-1] is ‘?’ or matches s[i-1]: The ? character can match exactly one character, or the characters at s[i-1] and p[j-1] are the same. Therefore, dp[i][j] depends on the match status of the preceding substrings (dp[i-1][j-1]).

Result
The value at dp[sLen][pLen] gives the final result, indicating whether the entire string s can be matched to the entire pattern p. This approach ensures that every possible substring and subpattern interaction is considered, leading to a comprehensive and correct evaluation of pattern matching as specified.

Code:

bool isMatch(char* s, char* p) {
    int sLen = strlen(s);
    int pLen = strlen(p);
    
    // dp[i][j] will be true if the first i characters of s match the first j characters of p
    bool dp[sLen + 1][pLen + 1];
    memset(dp, 0, sizeof(dp));
    
    // Empty pattern can match with empty string
    dp[0][0] = true;
    
    // Only '*' can match with empty string
    for (int j = 1; j <= pLen; j++) {
        if (p[j-1] == '*')
            dp[0][j] = dp[0][j-1];
    }
    
    // Fill the dp table
    for (int i = 1; i <= sLen; i++) {
        for (int j = 1; j <= pLen; j++) {
            if (p[j-1] == '*') {
                // '*' can match with any sequence: no characters or at least one character
                dp[i][j] = dp[i][j-1] || dp[i-1][j];
            } else if (p[j-1] == '?' || s[i-1] == p[j-1]) {
                // '?' can match any single character
                // If current characters match, derive from the previous characters' match status
                dp[i][j] = dp[i-1][j-1];
            }
        }
    }
    
    return dp[sLen][pLen];
}