String Matching with Wildcards
String Matching with Wildcards
In many scenarios, such as file searching and text processing, we need to determine if two strings match when one string may contain wildcard characters. The most common wildcard characters are * (matches any sequence of characters, including an empty sequence) and ? (matches any single character).
What are Wildcards?
Wildcards are special characters that can represent one or more other characters. They are used in search patterns to create flexible matches.
*(Asterisk): Matches any sequence of characters (including the empty sequence).?(Question Mark): Matches exactly one character.
Solutions:
Now let’s see how to implement string matching with wildcards in different programming languages: Java, Python, C, and C++.
1. Java
import java.util.Scanner;
public class WildcardMatching {
// Function to match two strings with wildcards
public static boolean isMatch(String s, String p) {
int sLen = s.length();
int pLen = p.length();
boolean[][] dp = new boolean[sLen + 1][pLen + 1];
// Base case: empty pattern matches empty string
dp[0][0] = true;
// Fill the table for patterns that start with *
for (int j = 1; j <= pLen; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 1];
}
}
// Fill the table
for (int i = 1; i <= sLen; i++) {
for (int j = 1; j <= pLen; 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[sLen][pLen];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the string: ");
String s = scanner.nextLine();
System.out.print("Enter the pattern: ");
String p = scanner.nextLine();
// Check and print if the strings match
if (isMatch(s, p)) {
System.out.println(s + " matches " + p);
} else {
System.out.println(s + " does not match " + p);
}
scanner.close();
}
}
2. Python
# Function to match two strings with wildcards
def is_match(s, p):
s_len = len(s)
p_len = len(p)
dp = [[False] * (p_len + 1) for _ in range(s_len + 1)]
# Base case: empty pattern matches empty string
dp[0][0] = True
# Fill the table for patterns that start with *
for j in range(1, p_len + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
# Fill the table
for i in range(1, s_len + 1):
for j in range(1, p_len + 1):
if p[j - 1] == '*':
dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[s_len][p_len]
# Input from user
s = input("Enter the string: ")
p = input("Enter the pattern: ")
# Check and print if the strings match
if is_match(s, p):
print(f"{s} matches {p}")
else:
print(f"{s} does not match {p}")
3. C++
#include <iostream>
#include <vector>
using namespace std;
// Function to match two strings with wildcards
bool isMatch(const string &s, const string &p) {
int sLen = s.length();
int pLen = p.length();
vector<vector<bool>> dp(sLen + 1, vector<bool>(pLen + 1, false));
// Base case: empty pattern matches empty string
dp[0][0] = true;
// Fill the table for patterns that start with *
for (int j = 1; j <= pLen; j++) {
if (p[j - 1] == '*') {
dp[0][j] = dp[0][j - 1];
}
}
// Fill the table
for (int i = 1; i <= sLen; i++) {
for (int j = 1; j <= pLen; j++) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[sLen][pLen];
}
int main() {
string s, p;
cout << "Enter the string: ";
getline(cin, s);
cout << "Enter the pattern: ";
getline(cin, p);
// Check and print if the strings match
if (isMatch(s, p)) {
cout << s << " matches " << p << endl;
} else {
cout << s << " does not match " << p << endl;
}
return 0;
}
4. C
#include <stdio.h>
#include <string.h>
#define MAX 1000
// Function to match two strings with wildcards
int isMatch(const char *s, const char *p) {
int sLen = strlen(s);
int pLen = strlen(p);
int dp[MAX][MAX];
// Initialize dp array to 0
memset(dp, 0, sizeof(dp));
// Base case: empty pattern matches empty string
dp[0][0] = 1;
// Fill the table for patterns that start with *
for (int j = 1; j <= pLen; j++) {
if (p[j - 1] == '*') {
dp[0][j] = dp[0][j - 1];
}
}
// Fill the table
for (int i = 1; i <= sLen; i++) {
for (int j = 1; j <= pLen; j++) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[sLen][pLen];
}
int main() {
char s[MAX], p[MAX];
printf("Enter the string: ");
gets(s);
printf("Enter the pattern: ");
gets(p);
// Check and print if the strings match
if (isMatch(s, p)) {
printf("%s matches %s\n", s, p);
} else {
printf("%s does not match %s\n", s, p);
}
return 0;
}
Explanation of Code:
Each code version defines an isMatch function to determine if two strings match when one of them contains wildcards.
Dynamic Programming: Uses a 2D array
dpwheredp[i][j]indicates if the firsticharacters of the string match the firstjcharacters of the pattern.Base Case: An empty pattern matches an empty string.
Filling the Table:
If the pattern character is
*, it matches zero or more characters from the string.If the pattern character is
?, it matches exactly one character.If characters match directly, they proceed as usual.
Sample Input & Output:
Input:
string = "hello"
pattern = "h*l?o"
Output: hello matches h*l?o
Input:
string = "world"
pattern = "w?r*d"
Output: world matches w?r*d
Conclusion:
Matching strings with wildcard characters is a common task that helps improve understanding of dynamic programming and pattern matching techniques in various programming languages.
** Please do subscribe my blog for future updates and share with your friends, if you find this informative **
Comments
Post a Comment