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 '*'.

Solutions:

Python

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        i, j = 0, 0
        star, sp = -1, -1
        while i < m:
            if j < n and (p[j] == '?' or s[i] == p[j]):
                i += 1
                j += 1
            elif j < n and p[j] == '*':
                star = j
                sp = i
                j += 1
            elif star != -1:
                j = star + 1
                sp += 1
                i = sp
            else:
                return False
        while j < n and p[j] == '*':
            j += 1
        return j == n

C#

public class Solution {
    public bool IsMatch(string s, string p) {
        int m = s.Length, n = p.Length;
        int i = 0, j = 0;
        int star = -1, sp = -1;
        while (i < m) {
            if (j < n && (p[j] == '?' || s[i] == p[j])) {
                i++;
                j++;
            } else if (j < n && p[j] == '*') {
                star = j;
                sp = i;
                j++;
            } else if (star != -1) {
                j = star + 1;
                sp++;
                i = sp;
            } else {
                return false;
            }
        }
        while (j < n && p[j] == '*') {
            j++;
        }
        return j == n;
    }
}

Java

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        int i = 0, j = 0;
        int star = -1, sp = -1;
        while (i < m) {
            if (j < n && (p.charAt(j) == '?' || s.charAt(i) == p.charAt(j))) {
                i++;
                j++;
            } else if (j < n && p.charAt(j) == '*') {
                star = j;
                sp = i;
                j++;
            } else if (star != -1) {
                j = star + 1;
                sp++;
                i = sp;
            } else {
                return false;
            }
        }
        while (j < n && p.charAt(j) == '*') {
            j++;
        }
        return j == n;
    }
}

Javascript

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    let m = s.length, n = p.length;
    let i = 0, j = 0;
    let star = -1, sp = -1;
    while (i < m) {
        if (j < n && (p[j] === '?' || s[i] === p[j])) {
            i++;
            j++;
        } else if (j < n && p[j] === '*') {
            star = j;
            sp = i;
            j++;
        } else if (star !== -1) {
            j = star + 1;
            sp++;
            i = sp;
        } else {
            return false;
        }
    }
    while (j < n && p[j] === '*') {
        j++;
    }
    return j === n;
};

Typescript

function isMatch(s: string, p: string): boolean {
    let m = s.length, n = p.length;
    let i = 0, j = 0;
    let star = -1, sp = -1;
    while (i < m) {
        if (j < n && (p[j] === '?' || s[i] === p[j])) {
            i++;
            j++;
        } else if (j < n && p[j] === '*') {
            star = j;
            sp = i;
            j++;
        } else if (star !== -1) {
            j = star + 1;
            sp++;
            i = sp;
        } else {
            return false;
        }
    }
    while (j < n && p[j] === '*') {
        j++;
    }
    return j === n;
}

PHP

class Solution {

    /**
     * @param String $s
     * @param String $p
     * @return Boolean
     */
    function isMatch($s, $p) {
        $m = strlen($s);
        $n = strlen($p);
        $i = 0;
        $j = 0;
        $star = -1;
        $sp = -1;
        while ($i < $m) {
            if ($j < $n && ($p[$j] === '?' || $s[$i] === $p[$j])) {
                $i++;
                $j++;
            } else if ($j < $n && $p[$j] === '*') {
                $star = $j;
                $sp = $i;
                $j++;
            } else if ($star !== -1) {
                $j = $star + 1;
                $sp++;
                $i = $sp;
            } else {
                return false;
            }
        }
        while ($j < $n && $p[$j] === '*') {
            $j++;
        }
        return $j === $n;
    }
}

I hope this helps! Let me know if you have any questions. Don’t forget to follow and give some like to support my content

https://medium.com/@araneznorman