Leetcode Wildcard Matching problem solution

In the Leetcode Wildcard Matching problem solution 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 ‘*’.

Solution in C Programming

bool
isMatch(char *s, char *p) {
  size_t len, i;
  bool *ans, result;

  len = strlen(s);
  ans = malloc((len + 1) * sizeof(bool));
  memset(ans + 1, 0, len * sizeof(bool));
  *ans = true;

  for ( ; *p != 0; ++p) {
    if (*p == '*') {
      for (i = 0; i < len; ++i)
        ans[i + 1] |= ans[i];
    } else {
      for (i = 0; i < len; ++i)
        ans[len - i] = ans[len - i - 1] & (s[len - i - 1] == *p || *p == '?');
      ans[0] = false;
    }
  }
  result = ans[len];
  free(ans);
  return result;
}

Solution in C++ Programming

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.length();
        int m = p.length();
        vector<vector<int>> dp(n+1,vector<int>(m+1));
        dp[0][0] = 1;
        // int flag=0;
        for(int i=1;i<=n;i++)
            dp[i][0] = 0;
        for(int i=1;i<=m;i++)
        {
            if(p[i-1]=='*')
                dp[0][i] = dp[0][i-1];
            else
                dp[0][i] = 0;
        }
        
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(s[i-1]==p[j-1] || p[j-1]=='?')
                    dp[i][j] = dp[i-1][j-1];
                else if(p[j-1] == '*')
                    dp[i][j] = dp[i-1][j] || dp[i][j-1] ;
                else
                    dp[i][j] = 0;
            }
        }
        return dp[n][m];
    }
};

Solution in Java Programming

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (p.charAt(i) == '*') count++;
        }
        if (count==0 && m != n) return false;
        else if (n - count > m) return false;
        
        boolean[] match = new boolean[m+1];
        match[0] = true;
        for (int i = 0; i < m; i++) {
            match[i+1] = false;
        }
        for (int i = 0; i < n; i++) {
            if (p.charAt(i) == '*') {
                for (int j = 0; j < m; j++) {
                    match[j+1] = match[j] || match[j+1]; 
                }
            } else {
                for (int j = m-1; j >= 0; j--) {
                    match[j+1] = (p.charAt(i) == '?' || p.charAt(i) == s.charAt(j)) && match[j];
                }
                match[0] = false;
            }
        }
        return match[m];
    }
}

Solution in Python Programming

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        s,p='+'+s,'+'+p  # create two new strings with a char added at the front
        m,n=len(s),len(p)
        if n-p.count('*')>m:
            return False
        dp=[[False]*m for _ in xrange(n)] # if dp[i][j], this means s[:j+1] can match p[:i+1]
        dp[0][0]=True
        for i in xrange(1,n):
            dp[i][0]=dp[i-1][0] and p[i]=='*'
            if p[i]!='*':
                for j in xrange(1,m):
                    dp[i][j]=dp[i-1][j-1] and (p[i]==s[j] or p[i]=='?')
            else:
                for j in xrange(1,m):
                    dp[i][j]=dp[i-1][j] or dp[i][j-1]
        return dp[-1][-1]

Solution in C# Programming

public class Solution {
        public bool IsMatch(string s, string p) {
        var dp = new bool[s.Length + 1];
        var nextDp = new bool[s.Length + 1];
        
        // Base case: dp(0, 0) = true
        dp[0] = true;
        
        // Calculate dp(1, *) and onwards
        for (var pLen = 1; pLen <= p.Length; pLen++)
        {
            for (var sLen = 0; sLen <= s.Length; sLen++)
            {
                if (p[pLen-1] == '*')
                {
                    nextDp[sLen] = dp[sLen] || (sLen > 0 && nextDp[sLen-1]);
                }
                else
                {
                    nextDp[sLen] = sLen > 0 && dp[sLen-1] && (p[pLen-1] == '?' || p[pLen-1] == s[sLen-1]);
                }
            }
            
            // swap the arrays
            var t = dp;
            dp = nextDp;
            nextDp = t;
        }
        
        return dp[s.Length];
    }
}

Also read,

By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.

Leave a Reply

Your email address will not be published. Required fields are marked *