Program to check : If two strings Match Where One String Contains Wildcard Character
Definition & Explanation
The task is to check if two strings match, where one string contains wildcard characters. Wildcard characters are special characters that can match any character or a range of characters. Common wildcard characters include * (matches zero or more characters) and ? (matches exactly one character).
Concept: To check if two strings match where one string contains wildcard characters, we need to compare each character of both strings while handling wildcard characters appropriately. Here’s how we can approach this:
- Initialization: Start with pointers pointing to the beginning of both strings.
- Matching:
- If the characters at the current positions of both strings are equal, move both pointers to the next character.
- If the character in the pattern string is a
*, keep moving the pointer in the pattern string until it points to a non-wildcard character. Store the current positions of both pointers as the potential match positions. - If the character in the pattern string is a
?, move both pointers to the next character.
- Check End Conditions:
- If both pointers reach the end of their respective strings simultaneously, return true (strings match).
- If the pattern string pointer reaches the end and the text string pointer has not reached the end, return false (strings do not match).
More Description
Program Logic
- Initialize pointers
iandjto 0 for the text and pattern strings, respectively. - Loop until one of the strings reaches its end.
- Inside the loop, handle different cases based on the current characters of the text and pattern strings:
- If the characters match or the pattern character is a
?, move both pointers to the next character. - If the pattern character is a
*, keep advancing the pattern pointer until it points to a non-wildcard character. Store the positions of both pointers as the potential match positions. - If none of the above cases match, return false.
- If the characters match or the pattern character is a
- After the loop, if the text string pointer has reached the end, check if the pattern string pointer is also at the end or if it points to a non-wildcard character (to ensure that all remaining characters in the pattern string are matched by
*).
C
Method 1 :
#include <stdio.h>
#include <stdbool.h>
bool isMatch(char *text, char *pattern) {
char *potentialMatchText = NULL, *potentialMatchPattern = NULL;
while (*text != '\0') {
if (*pattern == '?' || *pattern == *text) {
text++;
pattern++;
} else if (*pattern == '*') {
potentialMatchPattern = pattern;
potentialMatchText = text;
pattern++;
} else if (potentialMatchPattern != NULL) {
pattern = potentialMatchPattern + 1;
text = ++potentialMatchText;
} else {
return false;
}
}
while (*pattern == '*') {
pattern++;
}
return *pattern == '\0';
}
int main() {
char text[] = "hello";
char pattern[] = "h*o";
if (isMatch(text, pattern)) {
printf("Match found!\n");
} else {
printf("No match found!\n");
}
return 0;
}
Output :
C++
Method 1 :
#include <iostream>
#include <string>
using namespace std;
bool isMatch(string text, string pattern) {
string::size_type i = 0, j = 0;
string::size_type potentialMatchText = string::npos;
string::size_type potentialMatchPattern = string::npos;
while (i < text.length()) {
if (j < pattern.length() && (pattern[j] == '?' || pattern[j] == text[i])) {
i++;
j++;
} else if (j < pattern.length() && pattern[j] == '*') {
potentialMatchPattern = j;
potentialMatchText = i;
j++;
} else if (potentialMatchPattern != string::npos) {
j = potentialMatchPattern + 1;
i = ++potentialMatchText;
} else {
return false;
}
}
while (j < pattern.length() && pattern[j] == '*') {
j++;
}
return j == pattern.length();
}
int main() {
string text = "hello";
string pattern = "h*o";
if (isMatch(text, pattern)) {
cout << "Match found!" << endl;
} else {
cout << "No match found!" << endl;
}
return 0;
}
Output :
JAVA
Method 1 :
public class StringMatch {
public static boolean isMatch(String text, String pattern) {
int i = 0, j = 0;
int potentialMatchText = -1, potentialMatchPattern = -1;
while (i < text.length()) {
if (j < pattern.length() && (pattern.charAt(j) == '?' || pattern.charAt(j) == text.charAt(i))) {
i++;
j++;
} else if (j < pattern.length() && pattern.charAt(j) == '*') {
potentialMatchPattern = j;
potentialMatchText = i;
j++;
} else if (potentialMatchPattern != -1) {
j = potentialMatchPattern + 1;
i = ++potentialMatchText;
} else {
return false;
}
}
while (j < pattern.length() && pattern.charAt(j) == '*') {
j++;
}
return j == pattern.length();
}
public static void main(String[] args) {
String text = "hello";
String pattern = "h*o";
if (isMatch(text, pattern)) {
System.out.println("Match found!");
} else {
System.out.println("No match found!");
}
}
}
Output :
Python
Method 1 :
def is_match(text, pattern):
i = 0
j = 0
potential_match_text = -1
potential_match_pattern = -1
while i < len(text):
if j < len(pattern) and (pattern[j] == '?' or pattern[j] == text[i]):
i += 1
j += 1
elif j < len(pattern) and pattern[j] == '*':
potential_match_pattern = j
potential_match_text = i
j += 1
elif potential_match_pattern != -1:
j = potential_match_pattern + 1
i = potential_match_text + 1
potential_match_text += 1
else:
return False
while j < len(pattern) and pattern[j] == '*':
j += 1
return j == len(pattern)
# Test the function
text = "hello"
pattern = "h*o"
if is_match(text, pattern):
print("Match found!")
else:
print("No match found!")
Output :
Match found!