Pattern Matching

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
8 upvotes
Asked in companies
AppleAmazonSprinklr

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
abab 4
bat ball bat ball
Sample Output 1 :
True
Explanation For sample input 1 :
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”.
Sample Input 2 :
2
abbb 4
bat ball bat bat
abab 4
bat bat bat bat
Sample Output 2 :
False
False
Hint

Think of a solution using HashMap to map the character of the pattern to the words in the “words” array.

Approaches (2)
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.
Time Complexity

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

Space Complexity

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.

Code Solution
(100% EXP penalty)
Pattern Matching
Full screen
Console