Last Updated: 7 Mar, 2021

Pattern Matching

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

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.

Solve now