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*sforneveropen"
B = "neveropen"
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*sforneveropen"; string B = "neveropen"; 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*sforneveropen"; String B = "neveropen"; 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 codeif __name__=='__main__': A = "gee*sforneveropen" B = "neveropen" print(int(doMatch(A, B)))# this code is contributed by # Shashank_Sharma |
C#
// C# program for string matching withusing 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*sforneveropen"; String B = "neveropen"; 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*sforneveropen"; var B = "neveropen"; 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*sforneveropen"; $B = "neveropen"; echo doMatch($A, $B); // This code is contributed by Tushil.?> |
Output
1
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 Codeint 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 codeA = "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 codelet 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
