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).

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[0][0] = true; 
  for (int j = 1; j <= m; j++) 
    if (pattern[j - 1] == '*') 
      lookup[0][j] = lookup[0][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[0][0] = true; 
    for (int j = 1; j <= m; j++) 
      if (pattern.charAt(j - 1) == '*') 
        lookup[0][j] = lookup[0][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.

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

References