Skip to main content

Leetcode 44: Wildcard Matching

 

1. Problem Statement (Simple Explanation):


You’re given:

  • A string s (text).

  • A pattern p that may contain:

    • lowercase letters

    • '?' which matches any single character

    • '*' which matches any sequence of characters (including empty)

You must determine if the entire string s matches the entire pattern p (no partial match).


2. Examples:


Example 1:


Input: s = "aa", p = "a"

Pattern "a" is only one character; s has two characters → cannot match entire string.

Output: false


Example 2:


Input: s = "aa", p = "*"

'*' can match any sequence, including "aa".

Output: true


Example 3:


Input: s = "cb", p = "?a"

  • '?' matches 'c'

  • 'a' must match 'b' → mismatch

Output: false


Constraints:


  • 0 <= s.length, p.length <= 2000

  • s has only lowercase letters.

  • p has lowercase letters, '?', '*'.


3. Approaches Overview:


Common approaches:

  1. Greedy with backtracking on * positions – O(m+n) average, O(1) extra space; standard and efficient.

  2. Dynamic Programming (2D DP) – O(m·n) time, O(m·n) space (or O(n) space optimized).

For interviews & large constraints, the greedy two-pointer with * backtracking is usually preferred.

I’ll focus on that, and briefly mention DP.


4. Greedy Two-Pointer Algorithm with * Backtracking:


Intuition:


We scan the string s and pattern p from left to right:

Maintain:

  • i – index in s

  • j – index in p

  • starIdx – last position of '*' in p (-1 if none)

  • matchIdx – position in s corresponding to the match right after the last '*'

Rules:

  1. If p[j] is a letter or '?' and matches s[i]:

    • Move both pointers: i++, j++.

  2. If p[j] is '*':

    • Record its position: starIdx = j.

    • Record matchIdx = i (position in s where * starts matching).

    • Move j++ (treat * as matching empty for now).

  3. If there is a mismatch:

    • If we previously saw a '*' (starIdx != -1):

      • Backtrack: interpret the last '*' as matching one more character in s:

        • j = starIdx + 1

        • matchIdx++

        • i = matchIdx

    • Else:

      • No '*' to adjust → match fails → return false.

  4. After traversing s (i.e., i == len(s)):

    • There may still be remaining characters in p.

    • They must all be '*' to match empty; skip trailing '*'.

    • If j reaches len(p), match is successful; otherwise, fail.

This approach allows '*' to be flexibly expanded or shrunk as needed.


Pseudo-code (Greedy):



Complexity:


Let m = len(s), n = len(p):

  • Time: O(m + n) worst/typical case.

  • Space: O(1) extra.


5. DP Approach (High-level)(Optimal):


Define dp[i][j]:

  • true if s[0..i-1] matches p[0..j-1].

Transition:

  • If p[j-1] is a letter or '?':

    • dp[i][j] = dp[i-1][j-1] && (p[j-1] == s[i-1] or p[j-1] == '?')

  • If p[j-1] == '*':

    • dp[i][j] = dp[i][j-1] /* * as empty */ OR dp[i-1][j] /* * matches one more char */

Base cases:

  • dp[0][0] = true

  • dp[0][j] = dp[0][j-1] if p[0..j-1] are all '*'.

This yields an O(m·n) time solution.


6. Java code:



7. C code:



8. C++ code:



9. Python code:



10. JavaScript code:


Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more