You are given a pattern in the form of a string and a collection of words. Your task is to determine if the pattern string and the collection of words have the same order.
Note :
The strings are non-empty.
The strings only contain lowercase English letters.
The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow.
The first line of each test case contains the string pattern and an integer N, denoting the number of words in the collection.
The second line of each test case contains N-words.
For each test case print in a new line, “True” if the strings in the words array follow the same order as the order of the characters in the pattern string. Otherwise, print “False”.
You do not need to print anything, it has already been taken care of. Just implement the given function.
Output for each test case will be printed in a separate line.
1 <= T <= 100
1 <= |pattern| <= 5000,
1 <= N <= 5000
1 <= X <= 6
Time Limit: 1sec
1
abab 4
bat ball bat ball
True
In the given example, ‘a’ is present at the 1st and 3rd position, and ‘b’ is present at the 2nd and 4th position. Similarly, in the collection of words, “bat” is present at the 1st and 3rd position while “ball” is present at the 2nd and 4th position. Since the words are following the order of the pattern string, we print “True”.
2
abbb 4
bat ball bat bat
abab 4
bat bat bat bat
False
False
Think of a solution using HashMap to map the character of the pattern to the words in the “words” array.
The approach is to use hashing. We can maintain two HashMaps. One HashMap can be used to know which character corresponds to which word. The other HashMap can be used to know whether a particular word has already been matched with any other character or not.
So, for each character in the pattern, we check for its corresponding word in the first map. If the character is not present in the first map, then we check whether the current word is present in the second map If it is present, that means this word corresponds to any other character in the pattern. So, we instantly return false in that case. If the word is not present in the second map, then we add this word to the second map and make firstmap[char] = currentWord.
Otherwise, if the character is already present in the first map, then we check whether firstMap[char] equalscurrentWord. If they are equal, then continue in the loop, else return false.
Steps:
O(N), where N is the size of the string pattern.
We are traversing the entire pattern and comparing each character with its corresponding word in the “words” array. Hence, the time complexity is O(N).
O(M), where M is the number of unique words in the “words” array.
We need extra linear space to maintain the hashmap which tells us whether a string has already been matched or not. Note that we need constant extra space for the hashmap which is being used to keep a track of a character and its corresponding string as there can at most be 26 different characters.
All tags
Sort by
Interview problems
Easy Java solution||100%
import java.util.* ;
import java.io.*;
import java.util.ArrayList;
public class Solution {
public static boolean isPatternMatching(String pattern, ArrayList<String> words) { ArrayList<String> al=new ArrayList(Arrays.asList(pattern.split(""))); boolean res=true;
for(int i=0;i<al.size();i++){ if(al.lastIndexOf(al.get(i))!=words.lastIndexOf(words.get(i)))
res=false;
} return res;
}
}
Interview problems
USING UNORDERED_MAP
#include <bits/stdc++.h>
bool isPatternMatching(string pattern, vector<string>& words) {
if(words.size()!=pattern.size())
return false;
unordered_map<char,string> pw;
unordered_map<string,char> wp;
for(int i=0; i<pattern.length(); i++)
{
if(pw.find(pattern[i])!=pw.end() )
{
if(pw[pattern[i]]!=words[i] || wp[words[i]]!=pattern[i])
return false;
}
else
{
pw[pattern[i]]=words[i];
wp[words[i]]=pattern[i];
}
}
return true;
}
Interview problems
Solution using map
#include <bits/stdc++.h>
bool isPatternMatching(string pattern, vector<string>& words) {
map<char,vector<int>> mp;
for(int i=0;i<pattern.length();i++){
mp[pattern[i]].push_back(i);
}
map<string,vector<int>> mp2;
for(int i=0;i<words.size();i++){
mp2[words[i]].push_back(i);
}
vector<vector<int>> v1;
for(auto it: mp){
v1.push_back(it.second);
}
vector<vector<int>> v2;
for(auto it: mp2){
v2.push_back(it.second);
}
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
if(v1==v2) return true;
else return false;
}
Interview problems
Easy C++ solution
#include <bits/stdc++.h>
bool isPatternMatching(string pattern, vector<string>& words) {
if(pattern.length()!=words.size()) {
return false;
}
unordered_map<string,char>rev;
unordered_map<char,string>m;
for(int i=0;i<pattern.length();i++) {
if(m.find(pattern[i])==m.end()) {
if(rev.find(words[i])==rev.end()) {
m[pattern[i]]=words[i];
rev[words[i]]=pattern[i];
}
else {
return false;
}
}
else if(m[pattern[i]]!=words[i]) {
return false;
}
}
return true;
}Interview problems
Discussion thread on Interview Problem | Pattern Matching
Hey everyone, creating this thread to discuss the interview problem - Pattern Matching.
Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Pattern Matching
