Wildcard matching

One string contain wildcard characters, ? represent one skip * represent any number of skip even null. compare both string still pass?

Wildcard Pattern Matching

Problem

You are given a string str and a pattern pat. Write a function to check if the pattern matches the whole string.

The pattern can have two special characters:

• ? matches any single character.
• * matches any sequence of characters (it can also match an empty sequence).

Examples

Example 1

Input: str = "xaylmz", pat = "x?y*z"
Output: true

• x matches x.
• ? matches a.
• y matches y.
• * matches lm.
• z matches z.

Example 2

Input: str = "xyza", pat = "x*z"
Output: false

• The pattern ends with z, but the string ends with a.
• The extra a at the end is not matched by the pattern.

Main Idea

We compare the strings from the end. Let i point to the last character of str and j point to the last character of pat.

Base Cases

• Both strings are finished: We checked everything, so return true.
• str is finished, but pat is not: The pattern can match only if all its remaining characters are *. A * can match an empty sequence. If we see any other character, return false.
• pat is finished, but str is not: Some characters in str are left with nothing to match. Return false.

Main Cases

• Characters are equal, or the pattern has ?: This is a match. Move one step back in both strings.
• The pattern has *: This is the tricky part. We have two choices:
  • * matches empty: Ignore the star and move back in pat only. This is (i, j - 1).
  • * matches one character: Use the current character of str and keep the star. Move back in str only. This is (i - 1, j).
  • If any of these two choices works, the answer is true.
• Characters are different and there is no wildcard: Return false.

Example: How * Works

Let us take str = "abcd" and pat = "a*d".

• Last characters are d and d. They match. Now we check "abc" and "a*".
• The pattern has *. We try both choices:
  • Star matches empty: Check "abc" and "a". This fails, because c does not match a.
  • Star matches c: Check "ab" and "a*".
• Again, the pattern has *. We try both choices:
  • Star matches empty: Check "ab" and "a". This fails.
  • Star matches b: Check "a" and "a*".
• Again, the pattern has *. We try both choices:
  • Star matches empty: Check "a" and "a". They match. Now both strings are finished, so we return true.

So * matched "bc", and the answer is true.

Solution 1: Recursion + Memoization (Top-Down)

We write a recursive function and save each answer in a table. So we never solve the same problem twice.

var isMatch = function (s, p) {
    let m = s.length;
    let n = p.length;

    let dp = Array.from({ length: m }, () => Array(n));

    function recurr(i, j) {
        // both strings are finished
        if (j < 0 && i < 0) {
            return true;
        }

        // str is finished, check that all remaining pattern characters are *
        if (i < 0 && j >= 0) {
            for (let k = j; k >= 0; k--) {
                if (p[k] !== '*') {
                    return false;
                }
            }
            return true;
        }

        // pattern is finished but str is not
        if (i >= 0 && j < 0) {
            return false;
        }

        // answer is already saved
        if (dp[i][j] !== undefined) {
            return dp[i][j];
        }

        if (s[i] === p[j] || p[j] === '?') {
            // characters match, move back in both
            dp[i][j] = recurr(i - 1, j - 1);
        } else if (p[j] === '*') {
            // star matches empty OR star matches one character
            dp[i][j] = recurr(i, j - 1) || recurr(i - 1, j);
        } else {
            // characters do not match
            dp[i][j] = false;
        }

        return dp[i][j];
    }

    return recurr(m - 1, n - 1);
};

Complexity

• Time Complexity: O(m * n)
  • m is the length of str and n is the length of pat.
  • There are m * n different states, and each state is solved only once.
  • The loop that checks for * in the base case adds a small extra cost. In the worst case, the total is O(m * n + n * n).
• Space Complexity: O(m * n)
  • The dp table stores m * n values.
  • The recursion stack uses O(m + n) extra space.

Solution 2: Tabulation (Bottom-Up)

In this method, we do not use recursion. We use 1-based indexing, so we do not need negative indexes.

Here, dp[i][j] means: do the first i characters of str match the first j characters of pat?

var isMatch = function (s, p) {
    let m = s.length;
    let n = p.length;

    let dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));

    // both strings are empty, so they match
    dp[0][0] = true;

    // empty str can match the pattern only if it has all *
    for (let j = 1; j <= n; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }

    // Fill the table
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s[i - 1] === p[j - 1] || p[j - 1] === '?') {
                // characters match, copy the diagonal value
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] === '*') {
                // star matches empty OR star matches one character
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            } else {
                // characters do not match
                dp[i][j] = false;
            }
        }
    }

    return dp[m][n];
};

Complexity

• Time Complexity: O(m * n)
  • We use two loops, one inside the other.
  • Each cell is filled in constant time.
• Space Complexity: O(m * n)
  • The dp table has (m + 1) * (n + 1) cells.
  • There is no recursion stack.

Comparison

Summary

• This is a dynamic programming problem.
• ? always matches one character, so we move back in both strings.
• * has two choices: match empty or match one more character. If any choice works, the answer is true.
• If str is finished, the rest of the pattern must be all *.
• Both solutions run in O(m * n) time and use O(m * n) space.
• Tabulation avoids recursion, so it is safer for long strings.