2

Pattern Matching

Difficulty: EASY
Avg. time to solve
15 min
Success Rate
85%

Problem Statement
Suggest Edit

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
Where N is the size of the collection of words and X is the size of strings in the collection of words.

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
Explanation for sample input 2:
In the given pattern string, ‘b’ is present at 2nd, 3rd, and 4th positions but in the collection of words, the words at these positions are not the same. Hence, we print “False”.
In the given pattern string, ‘a’ is present at the 1st and 3rd position, and ‘b’ is present at the 2nd and 4th position. But in the “words” array, all the words are exactly the same. Hence, the answer is “False”.
Want to solve this problem? Login now to get access to solve the problems