Practice/Meta/Leetcode 44. Wildcard Matching

Leetcode 44. Wildcard Matching

CodingMust

Problem

You are given a text string and a pattern string containing special wildcard characters. Your task is to determine whether the entire text string matches the pattern according to these rules:

• ? matches exactly one character (any character)
• * matches zero or more characters (any sequence, including empty)
• All other characters must match exactly

Return true if the pattern matches the entire text string from beginning to end, and false otherwise.

Requirements

1. The pattern must match the entire text string (not just a substring)
2. ? wildcard matches exactly one character
3. * wildcard matches any sequence of zero or more characters
4. Regular characters in the pattern must match the same character in the text

Constraints

• 0 <= text.length, pattern.length <= 2000
• text contains only lowercase English letters
• pattern contains only lowercase English letters and the wildcards ? and *
• Your solution should handle multiple consecutive * characters efficiently
• Time complexity: Aim for O(m × n) where m and n are the lengths of text and pattern
• Space complexity: O(m × n) for dynamic programming approach, or O(1) for optimized greedy approach

Examples

Example 1:

Input: text = "aa", pattern = "a" Output: false Explanation: The pattern "a" only matches one character, but text has two characters.

Example 2:

Input: text = "aa", pattern = "*" Output: true Explanation: The '*' matches any sequence, including "aa".

Example 3:

Input: text = "cb", pattern = "?a" Output: false Explanation: '?' matches 'c', but then 'a' does not match 'b'.

Example 4:

Input: text = "adceb", pattern = "*a*b" Output: true Explanation: The first '*' matches empty string, 'a' matches 'a', the second '*' matches "dce", and 'b' matches 'b'.

Example 5:

Input: text = "acdcb", pattern = "a*c?b" Output: false Explanation: After 'a' and '*' matching "cd", we have 'c' matching 'c', but then '?' should match exactly one character before 'b'. However, there are two characters remaining ('d' and 'b'), so no valid match exists.