# 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

```go
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