What is the time complexity of Wildcard Matching?

The optimal solution has a time complexity of O(mn).

What data structures are used to solve Wildcard Matching?

This problem uses String, Dynamic Programming, Greedy, Recursion. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Wildcard Matching?

Insight 1: Dynamic Programming is a suitable approach because the problem exhibits overlapping subproblems (whether a substring of 's' matches a substring of 'p'). Insight 2: The '*' character is the most important case to handle. It can either match zero characters, one character, or many characters. The DP approach allows us to consider all these possibilities.

Which companies ask LeetCode 44. Wildcard Matching in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Bloomberg, Confluent and 14 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Wildcard Matching - LeetCode 44 Solution

Wildcard Matching - Complete Solution Guide

Wildcard Matching is LeetCode problem 44, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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: Inpu

Detailed Explanation

The problem asks us to implement wildcard pattern matching with two special characters: '?' and '*'. The '?' character matches any single character, while the '*' character matches any sequence of characters (including an empty sequence). The goal is to determine if the given pattern 'p' matches the entire input string 's'. It's crucial that the entire string 's' must be matched, not just a part of it.

Solution Approach

The provided solutions use dynamic programming to solve the wildcard matching problem. A 1D DP array is used to store the matching results. The pattern is preprocessed to remove consecutive '*' characters. The DP array 'dp[j]' represents whether the substring 's[0...i-1]' matches 'p[0...j-1]'. The code iterates through the input string 's' and the pattern 'p', updating the DP array based on the current characters in 's' and 'p'.

Step-by-Step Algorithm

Step 1: Preprocess the pattern 'p' to remove consecutive '*' characters. This optimization avoids redundant computations.
Step 2: Initialize a 1D DP array 'dp' of size 'n+1' (where 'n' is the length of the preprocessed pattern). dp[0] is set to true, meaning an empty pattern matches an empty string.
Step 3: Handle the case where the pattern starts with '*'. For all j from 1 to n, if p[j-1] == '*', dp[j] = dp[j-1]. This accounts for '*' matching an empty string at the beginning.
Step 4: Iterate through the input string 's' (from i=1 to m) and the pattern 'p' (from j=1 to n).
Step 5: Inside the inner loop, update 'dp[j]' based on the characters s[i-1] and p[j-1].
Step 6: If p[j-1] is '?' or matches s[i-1], then dp[j] = dp[j-1] (meaning the current characters match, so the match depends on the previous substring match).
Step 7: If p[j-1] is '*', then dp[j] = dp[j] || dp[j-1] (meaning '*' can either match the current character s[i-1] or match an empty string).
Step 8: If p[j-1] is neither '?', '*', nor s[i-1], then dp[j] = false (no match).
Step 9: After the iterations, dp[n] will contain the result: whether the entire string 's' matches the entire pattern 'p'.

Key Insights

Insight 1: Dynamic Programming is a suitable approach because the problem exhibits overlapping subproblems (whether a substring of 's' matches a substring of 'p').
Insight 2: The '*' character is the most important case to handle. It can either match zero characters, one character, or many characters. The DP approach allows us to consider all these possibilities.
Insight 3: Reducing consecutive '*' characters in the pattern 'p' to a single '*' can significantly improve efficiency and simplify the logic. For example, 'a***b' is the same as 'a*b'.

Complexity Analysis

Time Complexity: O(mn)

Space Complexity: O(n)

Topics

This problem involves: String, Dynamic Programming, Greedy, Recursion.

Companies

Asked at: Adobe, Amazon, Apple, Bloomberg, Confluent, Coupang, Coursera, Google, Instacart, Meta, Microsoft, Salesforce, Snap, Twilio, Two Sigma, Uber, Walmart Labs, X, Zoho.

Wildcard Matching | LeetCode 44

Hard

String Dynamic Programming Greedy Recursion

Time: O(mn)Space: O(n)

Solution Code

Available in:

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        if (n > 0) {
            StringBuilder p_chars = new StringBuilder();
            p_chars.append(p.charAt(0));
            for (int k = 1; k < n; k++) {
                if (p.charAt(k) == '*' && p.charAt(k - 1) == '*') {
                    continue;
                }
                p_chars.append(p.charAt(k));
            }
            p = p_chars.toString();
        }

        n = p.length();

        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[j] = dp[j - 1];
            }
        }

        for (int i = 1; i <= m; i++) {
            boolean prev = dp[0];
            dp[0] = false;

            for (int j = 1; j <= n; j++) {
                boolean temp = dp[j];

                if (p.charAt(j - 1) == '?' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    dp[j] = prev;
                } else if (p.charAt(j - 1) == '*') {
                    dp[j] = temp || dp[j - 1];
                } else {
                    dp[j] = false;
                }

                prev = temp;
            }
        }

        return dp[n];
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 44: Wildcard Matching - Detailed explanation and solution approaches.

Topics

String Dynamic Programming Greedy Recursion

Companies

AdobeAmazonAppleBloombergConfluentCoupangCourseraGoogle

Stats

Difficulty:Hard

Languages:4

Companies:19

Problem #:44

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Preprocess the pattern 'p' to remove consecutive '*' characters. This optimization avoids redundant computations.
2
Step 2: Initialize a 1D DP array 'dp' of size 'n+1' (where 'n' is the length of the preprocessed pattern). dp[0] is set to true, meaning an empty pattern matches an empty string.
3
Step 3: Handle the case where the pattern starts with '*'. For all j from 1 to n, if p[j-1] == '*', dp[j] = dp[j-1]. This accounts for '*' matching an empty string at the beginning.
4
Step 4: Iterate through the input string 's' (from i=1 to m) and the pattern 'p' (from j=1 to n).
5
Step 5: Inside the inner loop, update 'dp[j]' based on the characters s[i-1] and p[j-1].
6
Step 6: If p[j-1] is '?' or matches s[i-1], then dp[j] = dp[j-1] (meaning the current characters match, so the match depends on the previous substring match).
7
Step 7: If p[j-1] is '*', then dp[j] = dp[j] || dp[j-1] (meaning '*' can either match the current character s[i-1] or match an empty string).
8
Step 8: If p[j-1] is neither '?', '*', nor s[i-1], then dp[j] = false (no match).
9
Step 9: After the iterations, dp[n] will contain the result: whether the entire string 's' matches the entire pattern 'p'.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(mn)

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is determined by the nested loops that iterate through the string 's' and the pattern 'p'. The space complexity is determined by the size of the DP array, which is proportional to the length of the pattern 'p'.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Recursion with Memoization

A recursive solution can be implemented with memoization to avoid redundant computations. The function would recursively check if substrings of 's' and 'p' match, storing the results in a memoization table.

Time: O(m*n)Space: O(m*n)

Trade-offs: Recursion with memoization can be easier to understand for some, but it may have higher space complexity due to the memoization table and recursion stack. The iterative DP approach is generally more efficient in terms of space.

Greedy Approach (with backtracking)

A greedy solution may seem intuitive but is very complex to implement correctly and efficiently. The idea is to match characters one by one, and when encountering a '*', try to match it greedily. When a match fails, backtrack to a previous '*' and try a shorter match.

Time: O(m*n) in worst case (similar or potentially worse than DP)Space: O(1) excluding recursion stack in some implementations

Trade-offs: The greedy approach can be faster in some cases, but it is much more difficult to implement correctly and may have worse performance in the worst case. It's generally less reliable than the DP approach for this problem.

✨

Key Insights

1Insight 1: Dynamic Programming is a suitable approach because the problem exhibits overlapping subproblems (whether a substring of 's' matches a substring of 'p').
2Insight 2: The '*' character is the most important case to handle. It can either match zero characters, one character, or many characters. The DP approach allows us to consider all these possibilities.
3Insight 3: Reducing consecutive '*' characters in the pattern 'p' to a single '*' can significantly improve efficiency and simplify the logic. For example, 'a***b' is the same as 'a*b'.

📚

Key Terms Explained

For Students

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Recursion

A function that calls itself to solve smaller versions of the same problem.

Greedy Algorithm

Making the best choice at each step without looking ahead.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty string 's' and empty pattern 'p'. The code correctly handles this case by initializing dp[0] to true, resulting in a match.
Edge case 2: Pattern 'p' consists only of '*' characters. The code correctly handles this case by propagating the 'true' value along the DP array.
Edge case 3: String 's' is empty, but pattern 'p' has non-'*' characters. This results in a 'false' match, as it should.
Edge case 4: String 's' is not empty, but the pattern 'p' is empty. This also results in 'false' match, as it should.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling consecutive '*' characters correctly in the pattern 'p'. Failing to reduce 'a***b' to 'a*b' can lead to incorrect results and increased runtime.

✗Common mistake 2: Incorrectly updating the DP array when encountering the '*' character. Forgetting that '*' can match an empty string or not properly considering the previous state of the DP array.

✗Common mistake 3: Not understanding the base cases for empty strings and patterns. Failing to initialize the DP array correctly can lead to incorrect results.

✗Common mistake 4: Not completely understanding the problem statement of 'matching the entire string'. The code must ensure that all characters of 's' are matched, not just a prefix.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Text editors and IDEs use wildcard matching for searching and replacing text based on complex patterns.

🏦Real-world scenario 2: Operating systems use wildcard matching for file system navigation and searching (e.g., finding all files ending with '.txt').

🎮Real-world scenario 3: Network security systems use wildcard matching for identifying malicious patterns in network traffic (e.g., detecting specific sequences of bytes in network packets).

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

These problems test your ability to optimize. Start with a brute force solution, then improve.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 15, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

❓

Frequently Asked Questions

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Wildcard Matching"?

For this hard-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?