44. Wildcard Matching

Wildcard Matching

Problem Description

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

Approach) Dynamic Programming (DP)

dp[i][j]Represents whether to match when the regular idigit matches the digit of the string.j

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
  var dp = Array(p.length + 1).fill(0).map(_ => ({}));
  return test(s, p, 0, 0, dp);
};

var test = function (s, p, sIndex, pIndex, dp) {
  if (dp[pIndex][sIndex] !== undefined) return dp[pIndex][sIndex];

  var sNow = s[sIndex];
  var pNow = p[pIndex];
  var res = false;

  if (pNow === undefined) return sNow === undefined;
  if (sNow === undefined) {
    for (var i = pIndex; i < p.length; i++) {
      if (p[i] !== '*') return false;
    }
    return true;
  }

  if (sNow === pNow || pNow === '?') {
    res = test(s, p, sIndex + 1, pIndex + 1, dp);
  } else if (pNow === '*') {
    res = test(s, p, sIndex, pIndex + 1, dp) || test(s, p, sIndex + 1, pIndex + 1, dp) || test(s, p, sIndex + 1, pIndex, dp);
  }

  dp[pIndex][sIndex] = res;

  return res;
};

OR

var isMatch = function (s, p) {

     let dp = Array(s.length + 1).fill(Array(p.length + 1).fill(false));

    dp[0][0] = true;

    for (let j = 1; j <= p.length; j++) {

        if (p[j — 1] == “*”) {

            dp[0][j] = dp[0][j — 1];

        }

    }

    for (let i = 1; i < s.length + 1; i++) {

        for (let j = 1; j < p.length + 1; j++) {

            if (p[j — 1] == “?” || p[j — 1] == s[i — 1]) {

                dp[i][j] = dp[i][j] || dp[i — 1][j — 1];

            } else if (p[j — 1] == “*”) {

                dp[i][j] = dp[i — 1][j] || dp[i][j — 1];

            }

        }

    }

    return dp[s.length][p.length];

};

Approach) Greedy (Memo)

var isMatch = function (s, p) {
  let memo = [];
  const util = (i, j) => {
    if (i == s.length && j == p.length) {
      return true;
    }
    if (j >= p.length) {
      return false;
    }
    if (i >= s.length) {
      if (p[j] == "*") {
        return util(i, j + 1);
      } else {
        return false;
      }
    }
    if (memo[i] != null && memo[i][j] != null) {
      return memo[i][j];
    }
    if (memo[i] == null) {
      memo[i] = [];
    }
    if (memo[i] != null && memo[i][j] == null) {
      memo[i][j] = [];
    }
    if (s[i] == p[j] || p[j] == "?") {
      memo[i][j] = util(i + 1, j + 1);
      return memo[i][j];
    } else if (p[j] == "*") {
      memo[i][j] = util(i + 1, j) || util(i, j + 1);
      return memo[i][j];
    } else {
      return false;
    }
  };
  return util(0, 0);
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 44. Wildcard Matching

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!