LeetCode 44: Wildcard Matching Solution

Master LeetCode problem 44 (Wildcard Matching), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

44. Wildcard Matching

Hard

String Dynamic Programming Greedy Recursion

Problem Explanation

Explanation

To solve this problem, we can use a dynamic programming approach with a 2D dp array. We will iterate over the input string s and the pattern string p to fill in the dp array. At each step, we will consider the current characters in s and p and update the dp array based on the following conditions:

If the characters match or the pattern character is '?', we take the value from the diagonal element in the dp array.
If the pattern character is '*', we consider two possibilities - either we take the value from the left element or from the top element in the dp array.
If none of the above conditions apply, we mark the current dp cell as false.

Finally, the value in the bottom right cell of the dp array will indicate whether the entire input string matches the pattern.

Time complexity: O(m*n) where m is the length of input string s and n is the length of the pattern p.
Space complexity: O(m*n) for the dp array.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 44 (Wildcard Matching)?

This page provides optimized solutions for LeetCode problem 44 (Wildcard Matching) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 44 (Wildcard Matching)?

The time complexity for LeetCode 44 (Wildcard Matching) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 44 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 44 in Java, C++, or Python.

Back to LeetCode Solutions