Wild card 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'.

Example 4:

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

Explanation

State Transition

• Case 1: If the current pattern character matches the current input character or is a '?", mark the current cell as true.

• Case 2: If the current pattern character is a '*', mark the current cell as true if

  • [null match] the current input character can be matched by the previous pattern character

    • M[i][j] = M[i][j-1]

  • OR

  • [1+ match] the current character can be matched by the '*' if last input char is_match

    • can be thought of as "skipping" over the current input character

    • M[i][j] = M[i-1][j]

• Case 3: No match

State Definition

• i (int)

  • the index up to which the input is matched

• j (int)

  • the index up to which the pattern is matched

• is_match (bool):

  • True if for the given i, j the pattern+input substrings are a match

State Initialization (base case)

• i=0, j=0 is true

  • empty pattern matches the empty string

• i>0, j=0 is false

  • empty pattern cannot match non-empty string

• i=0, j>0 is true if the current pattern character is '*' and the previous is also a match

  • can be thought of as a 'leading asterisk' case

  • any leading characters which can match an empty string are true. Otherwise false

func Match(pattern string, input string) bool {
  // init memo matrix
  M := make([][]bool, len(input)+1)

  for i := 0; i <= len(input); i++ {
    M[i] = make([]bool, len(pattern)+1)
  }

  // base case
  // empty pattern matches empty string
  M[0][0] = true
  
  for i := 1; i <= len(input); i++ {
    // cannot match empty pattern against non-empty string
    M[i][0] = false
  }

  for j := 1; j <= len(pattern); j++ {
    // asterisks match empty string
    // iff they are leading
    if pattern[j-1] == '*' {
      M[0][j] = M[0][j-1]
    } else {
      M[0][j] = false // redundant
    }
  }

  //case 1: p[j - 1] == a[i - 1] || p[j - 1] == '?' . Inherit from diagonal
  //case 2: p[j - 1] == '*' 
  //case 2a: Match nothing, M[i][j] = M[i][j - 1]. Matching nothing against prev input char
  //case 2b: Match one or more, M[i][j] = M[i - 1][j]. Matching wildcard to cur input char
  //case 3: p[j - 1] != a[i - 1] False. Can not match no matter what

  for i := 1; i <= len(input); i++ {
    for j := 1; j <= len(pattern); j++ {
      if pattern[j - 1] == input[i - 1] || pattern[j - 1] == '?' {
        M[i][j] = M[i - 1][j - 1]
      } else if pattern[j - 1] == '*' {
        M[i][j] = M[i][j - 1] || M[i - 1][j]
      } else {
        M[i][j] = false
      }
    }  
  }
  return M[len(input)][len(pattern)]
}

TC: O(N^2)

SC: O(N^2) can be lowered to O(2N) as only two rows are relevant