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

Example 3

Example 4

Example 5

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

Follow up

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