Given an array of strings arr[] which contains patterns of characters and “*” denoting any set of characters including the empty string. The task is to find a string that matches all the patterns in the array.
Note: If there is no such possible pattern, print -1.
Examples:
Input: arr[] = {“pq*du*q”, “pq*abc*q”, “p*d*q”}
Output: pqduabcdq
Explanation:
Pattern “pqduabcdq” matches all the strings:
String 1:
First “*” can be replaced by a empty string.
Second “*” can be replaced by “abcdq”.
String 2:
First “*” can be replaced by “du”
Second “*” can be replaced by “d”
String 3:
First “*” can be replaced by “q”
Second “*” can be replaced by “uabcd”
Input: arr[] = {“a*c”, “*”}
Output: ac
Approach: The idea is to find the common prefix and suffix string in all the patterns and then the middle of every pattern can be replaced by the first or last “*” in every pattern. Below is the illustration of the approach:
- Create three empty strings that match with the prefix, suffix, and middle portion of every pattern.
- Iterate over every pattern in the array, For every pattern:
- Find the first and last “*” in the pattern.
- Iterate over the existing prefix and check that if it matches the current prefix of the pattern, If any character doesn’t match with the pattern, return -1.
- If there is some portion that is leftover in the prefix of the current pattern, then append it to the prefix of the common string.
- Similarly, match the suffix of the pattern.
- Finally, append all the middle characters of the string except the “*” in the middle initialized string for the common string.
- Finally, concatenate the portions of the common string that is the prefix, middle, and the suffix portion of the string.
Below is the implementation of the above approach:
C++
// C++ implementation to find the // string which matches // all the patterns#include<bits/stdc++.h>using namespace std;// Function to find a common string // which matches all the patternstring find(vector<string> S,int N){ // For storing prefix till // first most * without conflicts string pref; // For storing suffix till // last most * without conflicts string suff; // For storing all middle // characters between // first and last * string mid; // Loop to iterate over every // pattern of the array for (int i = 0; i < N; i++) { // Index of the first "*" int first = int( S[i].find_first_of('*') ); // Index of Last "*" int last = int( S[i].find_last_of('*') ); // Iterate over the first "*" for (int z = 0; z < int(pref.size()) && z < first; z++) { if (pref[z] != S[i][z]) { return "*"; } } // Prefix till first most * // without conflicts for (int z = int(pref.size()); z < first; z++) { pref += S[i][z]; } // Iterate till last // most * from last for (int z = 0; z < int(suff.size()) && int(S[i].size())-1-z > last; z++) { if (suff[z] != S[i][int(S[i].size())-1-z]) { return "*"; } } // Make suffix till last // most * without conflicts for (int z = int(suff.size()); int(S[i].size())-1-z > last; z++) { suff += S[i][int(S[i].size())-1-z]; } // Take all middle characters // in between first and last most * for (int z = first; z <= last; z++) { if (S[i][z] != '*') mid += S[i][z]; } } reverse(suff.begin(), suff.end()); return pref + mid + suff;}// Driver Codeint main() { int N = 3; vector<string> s(N); // Take all // the strings s[0]="pq*du*q"; s[1]="pq*abc*q"; s[2]="p*d*q"; // Method for finding // common string cout<<find(s,N); return 0;} |
Java
import java.util.*;public class Main { // Function to find a common string // which matches all the pattern public static String find(ArrayList<String> S,int N) { // For storing prefix till // first most * without conflicts String pref = ""; // For storing suffix till // last most * without conflicts String suff = ""; // For storing all middle // characters between // first and last * String mid = ""; // Loop to iterate over every // pattern of the array for (int i = 0; i < N; i++) { // Index of the first "*" int first = S.get(i).indexOf('*'); // Index of Last "*" int last = S.get(i).lastIndexOf('*'); // Iterate over the first "*" for (int z = 0; z < pref.length() && z < first; z++) { if (pref.charAt(z) != S.get(i).charAt(z)) { return "*"; } } // Prefix till first most * // without conflicts for (int z = pref.length(); z < first; z++) { pref += S.get(i).charAt(z); } // Iterate till last // most * from last for (int z = 0; z < suff.length() && S.get(i).length()-1-z > last; z++) { if (suff.charAt(z) != S.get(i).charAt(S.get(i).length()-1-z)) { return "*"; } } // Make suffix till last // most * without conflicts for (int z = suff.length(); S.get(i).length()-1-z > last; z++) { suff += S.get(i).charAt(S.get(i).length()-1-z); } // Take all middle characters // in between first and last most * for (int z = first; z <= last; z++) { if (S.get(i).charAt(z) != '*') mid += S.get(i).charAt(z); } } suff = new StringBuilder(suff).reverse().toString(); return pref + mid + suff; } // Driver Code public static void main(String[] args) { int N = 3; ArrayList<String> s = new ArrayList<>(); // Take all // the strings s.add("pq*du*q"); s.add("pq*abc*q"); s.add("p*d*q"); // Method for finding // common string System.out.println(find(s, N)); }}// This code is contributed by divyansh2212 |
Python3
# Python3 implementation # to find the string which # matches all the patterns# Function to find a common # string which matches all # the patterndef find(S, N): # For storing prefix # till first most * # without conflicts pref = "" # For storing suffix # till last most * # without conflicts suff = "" # For storing all middle # characters between # first and last * mid = "" # Loop to iterate over every # pattern of the array for i in range(N): # Index of the first "*" first = int(S[i].index("*")) # Index of Last "*" last = int(S[i].rindex("*")) # Iterate over the first "*" for z in range(len(pref)): if(z < first): if(pref[z] != S[i][z]): return "*" # Prefix till first most * # without conflicts for z in range(len(pref),first): pref += S[i][z]; # Iterate till last # most * from last for z in range(len(suff)): if(len(S[i]) - 1 - z > last): if(suff[z] != S[i][len(S[i]) - 1 - z]): return "*" # Make suffix till last # most * without conflicts for z in range(len(suff), len(S[i]) - 1 - last): suff += S[i][len(S[i]) - 1 - z] # Take all middle characters # in between first and last most * for z in range(first, last + 1): if(S[i][z] != '*'): mid += S[i][z] suff=suff[:: -1] return pref + mid + suff# Driver CodeN = 3s = ["" for i in range(N)]# Take all # the stringss[0] = "pq*du*q"s[1] = "pq*abc*q"s[2] = "p*d*q"# Method for finding# common stringprint(find(s, N))# This code is contributed by avanitrachhadiya2155 |
C#
// C# program to find the // string which matches // all the patternsusing System;using System.Collections.Generic;using System.Linq;class Program{ // Function to find a common string // which matches all the pattern static string Find(List<string> S, int N) { // For storing prefix till // first most * without conflicts string pref = ""; // For storing suffix till // last most * without conflicts string suff = ""; // For storing all middle // characters between // first and last * string mid = ""; // Loop to iterate over every // pattern of the array for (int i = 0; i < N; i++) { // Index of the first "*" int first = S[i].IndexOf('*'); // Index of Last "*" int last = S[i].LastIndexOf('*'); // Iterate over the first "*" for (int z = 0; z < pref.Length && z < first; z++) { if (pref[z] != S[i][z]) { return "*"; } } // Prefix till first most * // without conflicts for (int z = pref.Length; z < first; z++) { pref += S[i][z]; } // Iterate till last // most * from last for (int z = 0; z < suff.Length && S[i].Length - 1 - z > last; z++) { if (suff[z] != S[i][S[i].Length - 1 - z]) { return "*"; } } // Make suffix till last // most * without conflicts for (int z = suff.Length; S[i].Length - 1 - z > last; z++) { suff += S[i][S[i].Length - 1 - z]; } // Take all middle characters // in between first and last most * for (int z = first; z <= last; z++) { if (S[i][z] != '*') { mid += S[i][z]; } } } return pref + mid + new string(suff.Reverse().ToArray()); } // Driver code static void Main(string[] args) { int N = 3; // Take all // the strings List<string> S = new List<string>() { "pq*du*q", "pq*abc*q", "p*d*q" }; // Method for finding // common string Console.WriteLine(Find(S, N)); }}// This code is contributed by Prince Kumar |
Javascript
// Function to find a common string which matches all the patternfunction find(S, N) { // For storing prefix till first most * without conflicts let pref = ""; // For storing suffix till last most * without conflicts let suff = ""; // For storing all middle characters between first and last * let mid = ""; // Loop to iterate over every pattern of the array for (let i = 0; i < N; i++) { // Index of the first "*" const first = S[i].indexOf("*"); // Index of Last "*" const last = S[i].lastIndexOf("*"); // Iterate over the first "*" for (let z = 0; z < pref.length; z++) { if (z < first) { if (pref[z] !== S[i][z]) { return "*"; } } } // Prefix till first most * without conflicts for (let z = pref.length; z < first; z++) { pref += S[i][z]; } // Iterate till last most * from last for (let z = 0; z < suff.length; z++) { if (S[i].length - 1 - z > last) { if (suff[z] !== S[i][S[i].length - 1 - z]) { return "*"; } } } // Make suffix till last most * without conflicts for (let z = suff.length; z < S[i].length - 1 - last; z++) { suff += S[i][S[i].length - 1 - z]; } // Take all middle characters in between first and last most * for (let z = first; z <= last; z++) { if (S[i][z] !== "*") { mid += S[i][z]; } } } // Reverse the suffix suff = suff.split("").reverse().join(""); // Return the common string return pref + mid + suff;}// Driver Codeconst N = 3;const s = ["", "", ""];// Take all the stringss[0] = "pq*du*q";s[1] = "pq*abc*q";s[2] = "p*d*q";// Method for finding common stringconsole.log(find(s, N)); |
Output:
pqduabcdq
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!
