Home » Technical Interview Questions » String Interview Questions » String comparison containing wildcards

# String comparison containing wildcards

In String comparison containing wildcards problem, we have given two strings second string contains small alphabets and the first contains small alphabets and some wildcard patterns.

Wildcard patterns are:

?: we can replace this wildcard with any small alphabet.

*: we can replace this wildcard with any string. An empty string is also allowed.

Check if the first string can be converted into the second string by replacing wildcard patterns.

## Example

Input

xy*y?

xyyyxyx

Output

True

Explanation if * is replaced by yyx and ? is replaced by x then both strings become the same.

## Recursive approach for string comparison containing wildcards

Case 1: If a character in the first string is an alphabet.

If alphabets in both string matches then we check for the next character in both the strings else we return false.

Case 2: If a character in the first string is ‘?’.

We can replace ? with character in the second string. So we check for the next character in both the strings.

Case 3: If a character in the first string is ‘*’.

We can consider it as an empty string. So we check the next character of the first string and current character of the second string.

OR

We can consider it as a string that contains characters similar to the second string. So check the current character of the first string and the next character of the second string.

### Implementation

#### C++ code

```#include <stdio.h>
#include <stdbool.h>
bool match(char *first, char * second)
{
if (*first == '\0' && *second == '\0')
return true;
if (*first == '*' && *(first+1) != '\0' && *second == '\0')
return false;
if (*first == '?' || *first == *second)
return match(first+1, second+1);
if (*first == '*')
return match(first+1, second) || match(first, second+1);
return false;
}
void test(char *first, char *second)
{ match(first, second)? puts("Yes"): puts("No"); }
int main()
{
test("xy*y?", "xyyyxyx");
return 0;
}
```
`Yes`

#### Java code

```class Check
{
static boolean match(String first, String second)
{
if (first.length() == 0 && second.length() == 0)
return true;
if (first.length() > 1 && first.charAt(0) == '*' &&
second.length() == 0)
return false;
if ((first.length() > 1 && first.charAt(0) == '?') ||
(first.length() != 0 && second.length() != 0 &&
first.charAt(0) == second.charAt(0)))
return match(first.substring(1),
second.substring(1));
if (first.length() > 0 && first.charAt(0) == '*')
return match(first.substring(1), second) ||
match(first, second.substring(1));
return false;
}
static void test(String first, String second)
{
if (match(first, second))
System.out.println("Yes");
else
System.out.println("No");
}
public static void main(String[] args)
{
test("xy*y?", "xyyyxyx");

}```
`Yes`

## Dynamic programming approach for string comparison containing wildcards

The recursive approach will check all possible cases. Here, subproblem calls solved subproblem many times. So to avoid recalculation of the same subproblem we will use dynamic programming. We will memorize the output of a subproblem once it is calculated and will use it directly when we need to calculate it again. The time complexity of the dynamic programming approach is O(n*m).

READ  Delete consecutive same words in a sequence

### Implementation

#### C++ code

```#include <bits/stdc++.h>
using namespace std;
bool strmatch(char str[], char pattern[],
int n, int m)
{

if (m == 0)
return (n == 0);
bool lookup[n + 1][m + 1];
memset(lookup, false, sizeof(lookup));
lookup = true;
for (int j = 1; j <= m; j++)
if (pattern[j - 1] == '*')
lookup[j] = lookup[j - 1];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (pattern[j - 1] == '*')
lookup[i][j] = lookup[i][j - 1] ||
lookup[i - 1][j];
else if (pattern[j - 1] == '?' ||
str[i - 1] == pattern[j - 1])
lookup[i][j] = lookup[i - 1][j - 1];
else lookup[i][j] = false;
}
}
return lookup[n][m];
}
int main()
{
char str[] = "xyyyxyx";
char pattern[] = "xy*y?";
if (strmatch(str, pattern, strlen(str),
strlen(pattern)))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
```
`Yes`

#### Java code

```import java.util.Arrays;
public class check{
static boolean strmatch(String str, String pattern,
int n, int m)
{
if (m == 0)
return (n == 0);
boolean[][] lookup = new boolean[n + 1][m + 1];
for(int i = 0; i < n + 1; i++)
Arrays.fill(lookup[i], false);
lookup = true;
for (int j = 1; j <= m; j++)
if (pattern.charAt(j - 1) == '*')
lookup[j] = lookup[j - 1];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (pattern.charAt(j - 1) == '*')
lookup[i][j] = lookup[i][j - 1] ||
lookup[i - 1][j];
else if (pattern.charAt(j - 1) == '?' ||
str.charAt(i - 1) == pattern.charAt(j - 1))
lookup[i][j] = lookup[i - 1][j - 1];
else lookup[i][j] = false;
}
}

return lookup[n][m];
}

public static void main(String args[])
{
String str = "xyyyxyx";
String pattern = "xy*y?";
if (strmatch(str, pattern, str.length(),
pattern.length()))
System.out.println("Yes");
else
System.out.println("No");

}
}
```
`Yes`

### Complexity Analysis

Time complexity: O(m x n)  where n and m are the sizes of both strings.