Problem Statement
Wildcard Pattern Matcher
You are developing a file search utility for a cloud storage system. Users need to be able to search for files using wildcard patterns, where certain characters in the pattern can match any character or sequence of characters in the file name.
Your task is to implement a wildcard pattern matcher that supports two special characters:
?(question mark) - Matches any single character*(asterisk) - Matches any sequence of characters (including an empty sequence)
For example, the pattern "file?.txt" would match "file1.txt" and "fileA.txt", but not "file12.txt". The pattern "*.jpg" would match any file with a .jpg extension.
Write a function that takes a text string (representing a file name) and a pattern string, and returns true if the text matches the pattern, and false otherwise. The matching should cover the entire text string.
Examples
Example 1:
Input: text = "report.pdf", pattern = "*.pdf"
Output: true
Explanation: The '*' matches 'report', so the pattern matches the entire text.
Example 2:
Input: text = "document2023.docx", pattern = "document????.docx"
Output: true
Explanation: The four '?' characters match '2023', so the pattern matches the entire text.
Example 3:
Input: text = "image.png", pattern = "*.jpg"
Output: false
Explanation: The pattern cannot match the text because the extensions are different.
Constraints
- The text and pattern strings consist only of lowercase English letters and the special characters '?' and '*'.
- The length of the text string is between 0 and 100 characters.
- The length of the pattern string is between 0 and 100 characters.
Problem Breakdown
To solve this problem, we need to:
- The '?' character is straightforward as it matches exactly one character.
- The '*' character is more complex as it can match any sequence, including an empty one.
- A greedy approach for '*' might not work for all cases, so we need to consider backtracking or dynamic programming.
- The problem can be broken down into smaller subproblems by matching one character at a time.
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Wildcard Pattern Matcher
You are developing a file search utility for a cloud storage system. Users need to be able to search for files using wildcard patterns, where certain characters in the pattern can match any character or sequence of characters in the file name.
Your task is to implement a wildcard pattern matcher that supports two special characters:
?(question mark) - Matches any single character*(asterisk) - Matches any sequence of characters (including an empty sequence)
For example, the pattern "file?.txt" would match "file1.txt" and "fileA.txt", but not "file12.txt". The pattern "*.jpg" would match any file with a .jpg extension.
Write a function that takes a text string (representing a file name) and a pattern string, and returns true if the text matches the pattern, and false otherwise. The matching should cover the entire text string.
Examples
Example 1:
The '*' matches 'report', so the pattern matches the entire text.
Example 2:
The four '?' characters match '2023', so the pattern matches the entire text.
Example 3:
The pattern cannot match the text because the extensions are different.
Problem Breakdown
Constraints:
- The text and pattern strings consist only of lowercase English letters and the special characters '?' and '*'.
- The length of the text string is between 0 and 100 characters.
- The length of the pattern string is between 0 and 100 characters.
Key Insights:
The '?' character is straightforward as it matches exactly one character.
The '*' character is more complex as it can match any sequence, including an empty one.
A greedy approach for '*' might not work for all cases, so we need to consider backtracking or dynamic programming.
The problem can be broken down into smaller subproblems by matching one character at a time.
Real-World Application
This problem has several practical applications:
File Systems
Wildcard patterns are used in file systems for searching and filtering files.
Text Processing
Wildcard matching is used in text editors and search tools for pattern-based searching.
Database Queries
SQL LIKE queries use wildcard patterns for flexible string matching in databases.