String matching with * (that matches with any) in any of the two strings

0 0 7 minutes read

You are given two strings A and B. Strings also contains special character * . you can replace * with any alphabetic character. Finally, you have to tell whether it is possible to make both string same or not.

Examples:

Input : A = "gee*sforzambiatek"
        B = "zambiatek"
Output :Yes
Input :A = "abs*"
       B = "abds"
Output :No

Explanation: How we can solve above problem, Basically we three cases,

Case 1: Both strings contain * at a particular position, at that time we can replace both * with any character to make the string equal at that position.
Case 2: If one string has character and the other has * at that position. So, we can replace * with the same character in another string.
Case 3: If both strings has a character at that position, then they must be same, otherwise we can’t make them equal.

Implementation:

C++

// CPP program for string matching with *
#include <bits/stdc++.h>
using namespace std;
 
bool doMatch(string A, string B)
{
    for (int i = 0; i < A.length(); i++) 
 
        // if the string don't have *
        // then character at that position
        // must be same.
        if (A[i] != '*' && B[i] != '*') 
            if (A[i] != B[i])
               return false;
 
    return true;
}
 
int main()
{
    string A = "gee*sforzambiatek";
    string B = "zambiatek";
    cout << doMatch(A, B);
    return 0;
}

Java

// Java program for string matching with * 
import java.util.*;
 
public class GfG {
     
    // Function to check if the two
    // strings can be matched or not
    public static int doMatch(String A, String B) { 
     
        for (int i = 0; i < A.length(); i++){
       
            // if the string don't have * 
            // then character at that position 
            // must be same. 
            if (A.charAt(i) != '*' && B.charAt(i) != '*'){  
                if (A.charAt(i) != B.charAt(i)) 
                   return 0;
            }
        }
   
        return 1; 
    } 
     
    // Driver code 
    public static void main(String []args){
         
        String A = "gee*sforzambiatek"; 
        String B = "zambiatek"; 
        System.out.println(doMatch(A, B));
    }
}
 
// This code is contributed by Rituraj Jain

Python3

# Python3 program for string 
# matching with *
 
def doMatch(A, B):
     
    for i in range(len(A)):
         
        # if the string don't have *
        # then character t that position
        # must be same.
        if A[i] != '*' and B[i] != '*':
            if A[i] != B[i]:
                return False
    return True
 
#Driver code
if __name__=='__main__':
    A = "gee*sforzambiatek"
    B = "zambiatek"
    print(int(doMatch(A, B)))
 
# this code is contributed by 
# Shashank_Sharma

C#

// C# program for string matching with
using System;
     
class GfG 
{
     
    // Function to check if the two
    // strings can be matched or not
    public static int doMatch(String A, String B)
    { 
     
        for (int i = 0; i < A.Length; i++)
        {
         
            // if the string don't have * 
            // then character at that position 
            // must be same. 
            if (A[i] != '*' && B[i] != '*') 
                if (A[i] != B[i])
                    return 0;
        }
     
        return 1; 
    } 
     
    // Driver code 
    public static void Main(String []args)
    {
        String A = "gee*sforzambiatek"; 
        String B = "zambiatek"; 
        Console.WriteLine(doMatch(A, B));
    }
}
 
// This code contributed by Rajput-Ji

Javascript

<script>
// javascript program for string matching with * public class GfG {
 
    // Function to check if the two
    // strings can be matched or not
    function doMatch(A, B)
    {
 
        for (i = 0; i < A.length; i++)
        {
 
            // if the string don't have *
            // then character at that position
            // must be same.
            if (A.charAt(i) != '*' && B.charAt(i) != '*')
            {
                if (A.charAt(i) != B.charAt(i))
                    return 0;
            }
        }
 
        return 1;
    }
 
    // Driver code
        var A = "gee*sforzambiatek";
        var B = "zambiatek";
        document.write(doMatch(A, B));
 
// This code is contributed by aashish1995. 
</script>

PHP

<?php
// PHP program for string matching with * 
 
function doMatch($A, $B) 
{ 
    for ($i = 0; $i < strlen($A); $i++) 
 
        // if the string don't have * 
        // then character at that position 
        // must be same. 
        if ($A[$i] != '*' && $B[$i] != '*') 
            if ($A[$i] != $B[$i]) 
            return false; 
 
    return true; 
}
 
// Driver Code
$A = "gee*sforzambiatek"; 
$B = "zambiatek"; 
echo doMatch($A, $B); 
 
// This code is contributed by Tushil.
?>

Output

Time Complexity: O(N)

Auxiliary Space: O(1)

Two pointer Approach:

Steps:

If the lengths of strings A != B, return No because it’s not possible to make them the same.
Initialize two pointers, i=0 and j= 0, pointing to the first characters of strings A and B, respectively.
Iterate while both pointers are within the string bounds:
1. If the characters at pointers i and j are equal or either of them is , move both pointers to the next character.
2. If the character at pointer i is , move pointer j until the characters at pointers i and j are equal or until pointer j reaches the end of string B.
3. If pointer j reaches the end of string B and pointer i is not pointing to , return No because it’s not possible to make them the same.
4. If the characters at pointers i and j are not equal and pointer i is not , return No because it’s not possible to make them the same.
If both pointers have reached the end of their respective strings, return Yes because it’s possible to make them the same.
If either pointer i or j has not reached the end of its string, return No because it’s not possible to make them the same.

Below is the implementation of above approach:

C++

// C++ implementation of the above approach
#include <iostream>
using namespace std;
 
bool isPossibleToMakeSame(string A, string B)
{
    int lenA = A.length();
    int lenB = B.length();
 
    if (lenA != lenB)
        return false;
 
    int i = 0, j = 0;
    while (i < lenA && j < lenB) {
        if (A[i] == B[j] || A[i] == '*' || B[j] == '*') {
            i++;
            j++;
        }
        else if (A[i] == '*' && B[j] != '*') {
            while (B[j] != '*' && j < lenB)
                j++;
        }
        else if (A[i] != '*' && B[j] == '*') {
            while (A[i] != '*' && i < lenA)
                i++;
        }
        else {
            return false;
        }
    }
 
    if (i == lenA && j == lenB)
        return true;
    else
        return false;
}
 
// Driver Code
int main()
{
    string A = "abs*", B = "abds";
 
    if (isPossibleToMakeSame(A, B))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
 
    return 0;
}

Java

public class GFG {
 
    // Function to check if it is possible to make two
    // strings equal considering '*' as a wildcard character
    public static boolean isPossibleToMakeSame(String A,
                                               String B)
    {
        int lenA = A.length();
        int lenB = B.length();
 
        // If the lengths of the two strings are different,
        // they cannot be made equal
        if (lenA != lenB)
            return false;
 
        int i = 0, j = 0;
        while (i < lenA && j < lenB) {
            // If characters at the current positions match
            // or either of them is '*', move to the next
            // positions in both strings.
            if (A.charAt(i) == B.charAt(j)
                || A.charAt(i) == '*'
                || B.charAt(j) == '*') {
                i++;
                j++;
            }
            // If character in string A is '*', skip
            // characters in string B until the next '*'.
            else if (A.charAt(i) == '*'
                     && B.charAt(j) != '*') {
                while (B.charAt(j) != '*' && j < lenB)
                    j++;
            }
            // If character in string B is '*', skip
            // characters in string A until the next '*'.
            else if (A.charAt(i) != '*'
                     && B.charAt(j) == '*') {
                while (A.charAt(i) != '*' && i < lenA)
                    i++;
            }
            // If none of the conditions above are met, the
            // strings cannot be made equal.
            else {
                return false;
            }
        }
 
        // If both strings are completely traversed and are
        // equal in length, they can be made equal.
        return i == lenA && j == lenB;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String A = "abs*";
        String B = "abds";
 
        // Check if it is possible to make the strings equal
        // considering '*' as wildcard
        if (isPossibleToMakeSame(A, B))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code is contributed by shivamgupta310570

Python3

def isPossibleToMakeSame(A, B):
    lenA = len(A)
    lenB = len(B)
 
    # Check if the lengths of A and B are equal
    if lenA != lenB:
        return False
 
    i = 0
    j = 0
    while i < lenA and j < lenB:
        if A[i] == B[j] or A[i] == '*' or B[j] == '*':
            i += 1
            j += 1
        elif A[i] == '*' and B[j] != '*':
            # Skip characters in B until '*' is encountered or end of B
            while j < lenB and B[j] != '*':
                j += 1
        elif A[i] != '*' and B[j] == '*':
            # Skip characters in A until '*' is encountered or end of A
            while i < lenA and A[i] != '*':
                i += 1
        else:
            return False
 
    # Check if both A and B are fully traversed
    if i == lenA and j == lenB:
        return True
    else:
        return False
 
# Driver code
A = "abs*"
B = "abds"
 
if isPossibleToMakeSame(A, B):
    print("Yes")
else:
    print("No")
 
# THIS CODE IS CONTRIBUTED BY KANCHAN AGARWAL

Javascript

function isPossibleToMakeSame(A, B) {
    let lenA = A.length;
    let lenB = B.length;
 
    if (lenA !== lenB)
        return false;
 
    let i = 0, j = 0;
    while (i < lenA && j < lenB) {
        if (A[i] === B[j] || A[i] === '*' || B[j] === '*') {
            i++;
            j++;
        }
        else if (A[i] === '*' && B[j] !== '*') {
            while (B[j] !== '*' && j < lenB)
                j++;
        }
        else if (A[i] !== '*' && B[j] === '*') {
            while (A[i] !== '*' && i < lenA)
                i++;
        }
        else {
            return false;
        }
    }
 
    if (i === lenA && j === lenB)
        return true;
    else
        return false;
}
 
// Driver code
let A = "abs*";
let B = "abds";
 
if (isPossibleToMakeSame(A, B))
    console.log("Yes");
else
    console.log("No");
 
// THIS CODE IS CONTRIBUTED BY KANCHAN AGARWAL

Output

No

Time Complexity: O(N), where N is the length of the input strings A and B.

Auxiliary Space: O(1)

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 zambiatek!