44. Wildcard Matching

Description

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.

'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Constraints

• s could be empty or contains only lowercase letters a-z.

• p could be empty or contains only lowercase letters a-z, and characters like ? or *.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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 = "ab"

Output: true

Explanation: The first '' matches the empty sequence, while the second '' matches the substring "dce".

Example 5

Input: s = "acdcb", p = "a*c?b"

Output: false

Solutions

Solution 1

/**
 * Time complexity : O(min(S,P)) for the best case and better than O(SlogP) 
 *    for the average case, where S and P are lengths of the input string 
 *    and the pattern correspondingly.
 * Space complexity : O(1) since it's a constant space solution.
 */

class Solution {
    public boolean isMatch(String s, String p) {
        if(p.isEmpty()) return s.isEmpty();
        int sIndex = 0;
        int pIndex = 0;
        int starIndex = -1;
        int siIndex = -1;
        
        while(sIndex < s.length()) {
            if(pIndex < p.length() && 
               (p.charAt(pIndex) == '?' || s.charAt(sIndex) == p.charAt(pIndex))) {
                sIndex++;
                pIndex++;
            } else if(pIndex < p.length() && p.charAt(pIndex) == '*') {
                siIndex = sIndex;
                starIndex = pIndex;
                pIndex++;
            } else if(starIndex != -1) {
                sIndex = siIndex+1;
                pIndex = starIndex+1;
                siIndex++;
            } else {
                return false;
            }
        }
        
        while(pIndex < p.length() && p.charAt(pIndex) == '*') {
            pIndex++;
        }
        
        return pIndex == p.length();
    }
}

Solution 2

/**
 * Time complexity : O(SP) where S and P are lengths of the input string 
 *    and the pattern correspondingly.
 * Space complexity : O(SP) to keep the matrix.
 */

class Solution {
    public boolean isMatch(String s, String p) {
        if(p.equals(s) || p.equals("*")) return true;
        if(p.isEmpty() || s.isEmpty()) return false;

        int sLen = s.length(), pLen = p.length();
        boolean[][] dp = new boolean[sLen+1][pLen+1];
        dp[0][0] = true;
        
        for(int i = 1; i < pLen; i++) {
            if(p.charAt(i-1) == '*') {
                dp[0][i] = dp[0][i-1];
            }
        }
        
        for(int i = 1; i <= sLen; i++) {
            for(int j = 0; j <= pLen; j++) {
                if(j > 0 && 
                   (p.charAt(j-1) == '?' || p.charAt(j-1) == s.charAt(i-1))) {
                    dp[i][j] = dp[i-1][j-1];
                } else if(j > 0 && p.charAt(j-1) == '*') {
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                } else {
                    dp[i][j] = false;
                }
            }
        }
        
        return dp[sLen][pLen];
    }
}

Follow up

• Count the Number of matching characters in a pair of strings - GFG