Problem Statement
Email Filter System
You're developing an email filtering system for a corporate client. The system needs to identify and categorize emails based on specific patterns in the subject lines and sender addresses.
One critical feature is the ability to match strings against patterns that can contain wildcard characters. Your task is to implement a function that determines if a given string matches a pattern where:
- The pattern can contain regular characters that must match exactly.
- The '?' character in the pattern matches any single character in the string.
- The '*' character in the pattern matches any sequence of characters in the string (including an empty sequence).
This will allow the email system to filter messages using flexible patterns like "urgent*meeting" or "report-??-2023".
Examples
Example 1:
Input: text = "urgent-meeting", pattern = "urgent*"
Output: true
Explanation: The "*" in the pattern matches the "-meeting" part of the text.
Example 2:
Input: text = "quarterly-report", pattern = "*report"
Output: true
Explanation: The "*" matches "quarterly-" at the beginning of the text.
Example 3:
Input: text = "budget-2023", pattern = "budget-??23"
Output: true
Explanation: The two "?" characters match "20" in the text.
Example 4:
Input: text = "team-meeting", pattern = "team-*ing"
Output: true
Explanation: The "*" matches "meet" in the middle of the text.
Example 5:
Input: text = "project-update", pattern = "progress-*"
Output: false
Explanation: The text starts with "project" but the pattern requires "progress".
Constraints
- The input string and pattern can contain any printable ASCII characters.
- The length of both the string and pattern is between 0 and 100 characters.
- The pattern can contain any number of '*' and '?' wildcard characters.
- The matching should be case-sensitive (e.g., 'A' and 'a' are different characters).
Problem Breakdown
To solve this problem, we need to:
- We need to handle the '*' wildcard carefully as it can match any sequence, including an empty one.
- The '?' wildcard is simpler as it matches exactly one character.
- A recursive or dynamic programming approach can be used to solve this problem.
- We can break down the problem into smaller subproblems by matching one character at a time.
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Email Filter System
You're developing an email filtering system for a corporate client. The system needs to identify and categorize emails based on specific patterns in the subject lines and sender addresses.
One critical feature is the ability to match strings against patterns that can contain wildcard characters. Your task is to implement a function that determines if a given string matches a pattern where:
- The pattern can contain regular characters that must match exactly.
- The '?' character in the pattern matches any single character in the string.
- The '*' character in the pattern matches any sequence of characters in the string (including an empty sequence).
This will allow the email system to filter messages using flexible patterns like "urgent*meeting" or "report-??-2023".
Examples
Example 1:
The "*" in the pattern matches the "-meeting" part of the text.
Example 2:
The "*" matches "quarterly-" at the beginning of the text.
Example 3:
The two "?" characters match "20" in the text.
Example 4:
The "*" matches "meet" in the middle of the text.
Example 5:
The text starts with "project" but the pattern requires "progress".
Problem Breakdown
Constraints:
- The input string and pattern can contain any printable ASCII characters.
- The length of both the string and pattern is between 0 and 100 characters.
- The pattern can contain any number of '*' and '?' wildcard characters.
- The matching should be case-sensitive (e.g., 'A' and 'a' are different characters).
Key Insights:
We need to handle the '*' wildcard carefully as it can match any sequence, including an empty one.
The '?' wildcard is simpler as it matches exactly one character.
A recursive or dynamic programming approach can be used to solve this problem.
We can break down the problem into smaller subproblems by matching one character at a time.
Real-World Application
This problem has several practical applications:
Email Filtering
Pattern matching is essential for categorizing and filtering emails based on subject lines or sender addresses.
Content Filtering
Used in content management systems to filter and categorize documents based on patterns.
Security Systems
Pattern matching helps in detecting potentially malicious content or suspicious patterns in data.