Pattern Matching

Posted: 7 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1

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.
Try Problem