Wildcard Pattern Matching in Java
A method for comparing strings to patterns that might contain wildcard characters is called wildcard pattern matching. As placeholders, these wildcard characters can match one or more characters in the string under comparison.
The most often used characters as wildcards are :
1. '?' (Question Mark): It matches any one character.
2. Asterisk ('*'): Matches one or more characters.
Example 1:
Input: "a?e."
Output: "ate," "age," etc.
Explanation: Any other three-letter word with "a" as the first character, "e" as the last character, and any character in between would match this pattern accurately.
Example 2:
Input: "a*"
Output: "a," "aa", "ab", "abc", etc.
Explanation: Any other string beginning with "a" would match this pattern.
Approach: Naive
A standard naive method for matching wildcard patterns involves iterating over the string and the pattern character by character, searching for matches and managing wildcard characters ('*' and '?') as needed. The naive method looks at every possible match combination, even testing with different combinations when wildcard characters are present.
Here’s the implementation of the naive approach :
FileName: WildcardPatternMatching.java
public class WildcardPatternMatching {
public static boolean isMatch(String str, String pattern) {
return isMatch(str, 0, pattern, 0);
}
private static boolean isMatch(String str, int sIndex, String pattern, int pIndex) {
// Base cases: if both string and pattern reach their ends
if (sIndex == str.length() && pIndex == pattern.length()) {
return true;
}
if (pIndex == pattern.length()) {
return false;
}
// If only the string reaches its end, then check if the remaining pattern consists of only '*'
if (sIndex == str.length()) {
while (pIndex < pattern.length() && pattern.charAt(pIndex) == '*') {
pIndex++;
}
return pIndex == pattern.length();
}
// If characters match or pattern has '?'
if (str.charAt(sIndex) == pattern.charAt(pIndex) || pattern.charAt(pIndex) == '?') {
return isMatch(str, sIndex + 1, pattern, pIndex + 1);
}
if (pattern.charAt(pIndex) == '*') {
return isMatch(str, sIndex, pattern, pIndex + 1) || isMatch(str, sIndex + 1, pattern, pIndex);
}
return false;
}
public static void main(String args[]) {
String str = "Java";
String pattern = "J*a";
if (isMatch(str, pattern)) {
System.out.println("Pattern matches the string.");
} else {
System.out.println("Pattern does not match the string.");
}
}
}
Output:
Pattern matches the string.
Complexity analysis: Wildcard pattern matching has an exponential time complexity of O(2^(m+n)) due to exploring all possible matches and potential stack usage, including backtracking. The space complexity of the naive wildcard pattern matching method is O(m + n), mostly because of recursive calls and auxiliary space used for intermediate results.
Approach: Optimized
Wildcard pattern matching can be optimized using techniques like dynamic programming, memorization-based backtracking, or iterative methods to enhance algorithm efficiency.
Here’s the implementation of the optimized approach:
FileName: WildcardPatternMatching1.java
public class WildcardPatternMatching1 {
public static boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
// Dynamic programming table to store matching results
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
// Handling patterns starting with '*'
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 1];
}
}
// Fill the dp table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
// Matching characters or '?' at current positions
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == '*') {
// '*' can match zero or more characters
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
}
return dp[m][n];
}
public static void main(String args[]) {
String str = "Java";
String pattern = "J*a";
// Checking if the pattern matches the string
if (isMatch(str, pattern)) {
System.out.println("Pattern matches the string.");
} else {
System.out.println("Pattern does not match the string.");
}
}
}
Output:
Pattern matches the string.
Complexity analysis: The time and space complexity of the optimal method for matching wildcard patterns using dynamic programming is O(m * n), where m is the length of the string and n is the length of the pattern. Because it can handle big strings and patterns in a reasonable amount of time and memory, this makes it efficient for real-world use cases.