Given two strings where first string may contain wild card characters and second string is a normal string. Write a function that returns true if the two strings match. The following are allowed wild card characters in first string.
* --> Matches with 0 or more instances of any character or set of characters. ? --> Matches with any one character.
For example, “g*ks” matches with “neveropen” match. And string “ge?ks*” matches with “neveropen” (note ‘*’ at the end of first string). But “g*k” doesn’t match with “gee” as character ‘k’ is not present in second string.
C++
// A C program to match wild card characters #include <stdbool.h> #include <stdio.h> // The main function that checks if two given strings // match. The first string may contain wildcard characters bool match(char* first, char* second) { // If we reach at the end of both strings, we are done if (*first == '\0' && *second == '\0') return true; // Make sure to eliminate consecutive '*' if (*first == '*') { while (*(first + 1) == '*') first++; } // Make sure that the characters after '*' are present // in second string. This function assumes that the // first string will not contain two consecutive '*' if (*first == '*' && *(first + 1) != '\0' && *second == '\0') return false; // If the first string contains '?', or current // characters of both strings match if (*first == '?' || *first == *second) return match(first + 1, second + 1); // If there is *, then there are two possibilities // a) We consider current character of second string // b) We ignore current character of second string. if (*first == '*') return match(first + 1, second) || match(first, second + 1); return false; } // A function to run test cases void test(char* first, char* second) { match(first, second) ? puts("Yes") : puts("No"); } // Driver program to test above functions int main() { test("g*ks", "neveropen"); // Yes test("ge?ks*", "neveropen"); // Yes test("g*k", "gee"); // No because 'k' is not in second test("*pqrs", "pqrst"); // No because 't' is not in first test("abc*bcd", "abcdhghgbcd"); // Yes test("abc*c?d", "abcd"); // No because second must have // 2 instances of 'c' test("*c*d", "abcd"); // Yes test("*?c*d", "abcd"); // Yes test("neveropen**", "neveropen"); // Yes return 0; } |
Java
// Java program to match wild card characters class GFG { // The main function that checks if // two given strings match. The first string // may contain wildcard characters static boolean match(String first, String second) { // If we reach at the end of both strings, // we are done if (first.length() == 0 && second.length() == 0) return true; // Make sure to eliminate consecutive '*' if (first.length() > 1 &&first.charAt(0) == '*') { int i=0; while (i+1<first.length() && first.charAt(i+1) == '*') i++; first=first.substring(i); } // Make sure that the characters after '*' // are present in second string. // This function assumes that the first // string will not contain two consecutive '*' if (first.length() > 1 && first.charAt(0) == '*' && second.length() == 0) return false; // If the first string contains '?', // or current characters of both strings match 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 there is *, then there are two possibilities // a) We consider current character of second string // b) We ignore current character of second string. if (first.length() > 0 && first.charAt(0) == '*') return match(first.substring(1), second) || match(first, second.substring(1)); return false; } // A function to run test cases static void test(String first, String second) { if (match(first, second)) System.out.println("Yes"); else System.out.println("No"); } // Driver Code public static void main(String[] args) { test("g*ks", "neveropen"); // Yes test("ge?ks*", "neveropen"); // Yes test("g*k", "gee"); // No because 'k' is not in second test("*pqrs", "pqrst"); // No because 't' is not in first test("abc*bcd", "abcdhghgbcd"); // Yes test("abc*c?d", "abcd"); // No because second must have 2 // instances of 'c' test("*c*d", "abcd"); // Yes test("*?c*d", "abcd"); // Yes test("neveropen**", "neveropen"); // Yes } } // This code is contributed by // sanjeev2552 |
Python3
# Python program to match wild card characters # The main function that checks if two given strings match. # The first string may contain wildcard characters def match(first, second): # If we reach at the end of both strings, we are done if len(first) == 0 and len(second) == 0: return True # Make sure to eliminate consecutive '*' if len(first) > 1 and first[0] == '*': i = 0 while i+1 < len(first) and first[i+1] == '*': i = i+1 first = first[i:] # Make sure that the characters after '*' are present # in second string. This function assumes that the first # string will not contain two consecutive '*' if len(first) > 1 and first[0] == '*' and len(second) == 0: return False # If the first string contains '?', or current characters # of both strings match if (len(first) > 1 and first[0] == '?') or (len(first) != 0 and len(second) != 0 and first[0] == second[0]): return match(first[1:], second[1:]) # If there is *, then there are two possibilities # a) We consider current character of second string # b) We ignore current character of second string. if len(first) != 0 and first[0] == '*': return match(first[1:], second) or match(first, second[1:]) return False # A function to run test cases def test(first, second): if match(first, second): print("Yes") else: print("No") # Driver program test("g*ks", "neveropen") # Yes test("ge?ks*", "neveropen") # Yes test("g*k", "gee") # No because 'k' is not in second test("*pqrs", "pqrst") # No because 't' is not in first test("abc*bcd", "abcdhghgbcd") # Yes test("abc*c?d", "abcd") # No because second must have 2 instances of 'c' test("*c*d", "abcd") # Yes test("*?c*d", "abcd") # Yes test("neveropen**", "neveropen") # Yes # This code is contributed by BHAVYA JAIN and ROHIT SIKKA |
C#
// C# program to match wild card characters using System; class GFG { // The main function that checks if // two given strings match. The first string // may contain wildcard characters static bool match(String first, String second) { // If we reach at the end of both strings, // we are done if (first.Length == 0 && second.Length == 0) return true; // Make sure to eliminate consecutive '*' if (first.Length > 1 && first[0] == '*') { int i = 0; while (i + 1 < first.Length && first[i + 1] == '*') i++; first = first.Substring(i); } // Make sure that the characters after '*' // are present in second string. // This function assumes that the first // string will not contain two consecutive '*' if (first.Length > 1 && first[0] == '*' && second.Length == 0) return false; // If the first string contains '?', // or current characters of both strings match if ((first.Length > 1 && first[0] == '?') || (first.Length != 0 && second.Length != 0 && first[0] == second[0])) return match(first.Substring(1), second.Substring(1)); // If there is *, then there are two possibilities // a) We consider current character of second string // b) We ignore current character of second string. if (first.Length > 0 && first[0] == '*') return match(first.Substring(1), second) || match(first, second.Substring(1)); return false; } // A function to run test cases static void test(String first, String second) { if (match(first, second)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } // Driver Code public static void Main(String[] args) { test("g*ks", "neveropen"); // Yes test("ge?ks*", "neveropen"); // Yes test("g*k", "gee"); // No because 'k' is not in second test("*pqrs", "pqrst"); // No because 't' is not in first test("abc*bcd", "abcdhghgbcd"); // Yes test("abc*c?d", "abcd"); // No because second must // have 2 instances of 'c' test("*c*d", "abcd"); // Yes test("*?c*d", "abcd"); // Yes test("neveropen**", "neveropen"); // Yes } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to match wild card characters // The main function that checks if // two given strings match. The first string // may contain wildcard characters function match(first, second) { // If we reach at the end of both strings, // we are done if (first.length == 0 && second.length == 0) return true; // Make sure that the characters after '*' // are present in second string. // This function assumes that the first // string will not contain two consecutive '*' if (first.length > 1 && first[0] == '*' && second.length == 0) return false; // If the first string contains '?', // or current characters of both strings match if ((first.length > 1 && first[0] == '?') || (first.length != 0 && second.length != 0 && first[0] == second[0])) return match(first.substring(1), second.substring(1)); // If there is *, then there are two possibilities // a) We consider current character of second string // b) We ignore current character of second string. if (first.length > 0 && first[0] == '*') return match(first.substring(1), second) || match(first, second.substring(1)); return false; } // A function to run test cases function test(first, second) { if (match(first, second)) document.write("Yes" + "<br>"); else document.write("No" + "<br>"); } // Driver code test("g*ks", "neveropen"); // Yes test("ge?ks*", "neveropen"); // Yes test("g*k", "gee"); // No because 'k' is not in second test("*pqrs", "pqrst"); // No because 't' is not in first test("abc*bcd", "abcdhghgbcd"); // Yes test("abc*c?d", "abcd"); // No because second must have 2 // instances of 'c' test("*c*d", "abcd"); // Yes test("*?c*d", "abcd"); // Yes // This code is contributed by SoumikMondal </script> |
Output:
Yes Yes No No Yes No Yes Yes Yes
Time Complexity: O(n)
Auxiliary Space: O(1)
Exercise
1) In the above solution, all non-wild characters of first string must be there is second string and all characters of second string must match with either a normal character or wildcard character of first string. Extend the above solution to work like other pattern searching solutions where the first string is pattern and second string is text and we should print all occurrences of first string in second.
2) Write a pattern searching function where the meaning of ‘?’ is same, but ‘*’ means 0 or more occurrences of the character just before ‘*’. For example, if first string is ‘a*b’, then it matches with ‘aaab’, but doesn’t match with ‘abb’.
This article is compiled by Vishal Chaudhary and reviewed by neveropen team. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
