Pattern Matching
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.

Input Format :

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.

Output Format :

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”.

Note :

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.

Constraints :

1

Question

Pattern Matching

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.

Input Format :

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.

Output Format :

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”.

Note :

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.

Constraints :

1 <= T <= 100
1 <= |pattern| <= 5000, 
1 <= N <= 5000
1 <= X <= 6

Time Limit: 1sec

Accepted Answer

Using Hashing

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:

Create two HashMaps, charToString and alreadyMatched. The map, charToString maps characters in the pattern to the strings in the “words” array. The map, alreadyMatchedstates whether a string is previously matched to any other character.
If pattern.size() != words.size(), return False.
Run a loop from i=0 to pattern.size() and do:
- If (charToString[pattern[i]] == “”):
  - If alreadyMatched[words[i]] == true, return false, as this word is already mapped to some other character previously.
  - Make charToString[pattern[i]] = words[i].
  - Make alreadyMatched[words[i]] = true.
- Else:
  - If charToString[pattern[i]] != words[i], return False.
Finally, as there is no mismatch we can return True.

Space Complexity: OtherExplanation:

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.

Time Complexity: O(n)Explanation:

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).

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(M),



    Where N is the length of the pattern string and M is the number of unique words in the collection.

'''



def isPatternMatching(pattern, words):



	# Maintain a HashMap to keep a track of the corresponding characters and strings.

    charToString = dict()



	# Maintain another HashMap to keep a track of whether a string has already been matched or not.

    alreadyMatched = dict()



	# If the size of the pattern string is not equal to the size of the string array, return False.

    if(len(pattern) != len(words)):

        return False



    for i in range(len(pattern)):

        if pattern[i] not in charToString:

            if words[i] in alreadyMatched:

                return False



            charToString[pattern[i]] = words[i]

            alreadyMatched[words[i]] = True



        else:

            if charToString[pattern[i]] != words[i]:

                return False



	# If there is no mismatch, return True.

    return True

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(M),



	Where N is the length of the pattern string and M is the number of unique words in the collection.

*/



#include

#include



bool isPatternMatching(string pattern, vector words) {



	// Maintain a HashMap to keep a track of the corresponding characters and strings.

	unordered_map charToString;



	// Maintain another HashMap to keep a track of whether a string has already been matched or not.

	unordered_map alreadyMatched;



	// If the size of the pattern string is not equal to the size of the string array, return False.

	if (pattern.size() != words.size()) 

    {

		return false;

	}



	for (int i = 0; i < pattern.size(); i++) 

    {



		if (charToString[pattern[i]] == "") 

        {

			if (alreadyMatched[words[i]]) 

            {

				return false;

			}



			charToString[pattern[i]] = words[i];

			alreadyMatched[words[i]] = true;

		}



		else 

        {

			if (charToString[pattern[i]] != words[i]) 

            {

				return false;

			}

		}

	}



	// If there is no mismatch, return True.

	return true;

}

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(M),



	Where N is the length of the pattern string and M is the number of unique words in the collection.

*/



import java.util.ArrayList;

import java.util.HashMap;



public class Solution {

    public static boolean isPatternMatching(String pattern, ArrayList words) 

    {

        // Maintain a HashMap to keep a track of the corresponding characters and strings.

	    HashMap charToString = new HashMap<>();



	    // Maintain another HashMap to keep a track of whether a string has already been matched or not.

	    HashMap alreadyMatched = new HashMap<>();



	    // If the size of the pattern string is not equal to the size of the string array, return False.

	    if (pattern.length() != words.size()) 

        {

		    return false;

	    }



	    for (int i = 0; i < pattern.length(); i++) 

        {

		    if (charToString.containsKey(pattern.charAt(i)) == false) 

            {

			    if (alreadyMatched.containsKey(words.get(i))) 

                {

				   return false;

			    }



			    charToString.put(pattern.charAt(i), words.get(i));

			    alreadyMatched.put(words.get(i), true);

		    }  

            else 

            {   

			    if (charToString.get(pattern.charAt(i)).equals(words.get(i)) == false) 

                {

				    return false;

			    }

		    }

	    }



	    // If there is no mismatch, return True.

	    return true;

    }

}

Accepted Answer

Using single HashMap

The approach is to use a single HashMap. This HashMap can be used to store the index of the first occurrence of each character in the pattern and the index of the first occurrence of every unique string in the “words” array. If the current character is not present in the HashMap already, that means that the current index is the first occurrence of this character. Similarly, we can store the index of the first occurrence of every string. If the indices of the first occurrences of the present character and the present string do not match we can return False. If there is no mismatch, we can return True.

Note that, since in languages like c++, there is a difference between characters and strings, so we need to convert each character in the “pattern” to a string. It may also happen that the word in the “words” array can consist of only one character. In that case, a collision occurs and the algorithm might give incorrect results. For example, if the pattern is “abab” and “words” array is {“bat”, “a”, “bat”, “a”}. Then, this will give the wrong output. So, we add an extra character ‘_’ to each word in the “words” array to overcome this issue.

Steps:

Initialize a HashMap getIndex to store the indices.
If pattern.size() != words.size(), return False.
Run a loop from i=0 to pattern.size() and do:
- Store the character at pattern[i] in a string charInPattern.
- If this character is not already present in the HashMap, then make getIndex[charInPattern] = i.
- Store the string at words[i] in a string word and add any special character at the end of it to differentiate it from a character of the pattern string, i.e word = words[i] + ‘_’
- If this string is not already present in the HashMap, then make getIndex[word] = i.
- Now, check for the indices of the current character and the current word. If these indices do not match, then return False, i.e., if(getIndex[charInPattern] != getIndex[word], return False.
- If there is no mismatch, return True.

Space Complexity: OtherExplanation:

O(M), where M is the number of unique words in the collection.

We need extra linear space to maintain the hashmap as we need to store indices of the first occurrences of all unique strings in the collection of words.