Match Specific Pattern

Let the list of words be {cod, zcz} and the pattern be ‘nin’. For each word in the list, we will check whether the word matches the pattern or not: For the word ‘cod’: Letter ‘n’ in the pattern maps to letter ‘c’ in the word. Letter ‘i’ in the pattern maps to letter ‘o’ in the word. Letter ‘n’ in the pattern maps to letter ‘d’ in the word. As the same letter ‘n’ in the pattern, maps to two different letters ‘c’ and ‘d’ in the word. Hence, ‘cod’ is not a valid match. For the word 'zcz': Letter ‘n’ in the pattern maps to letter ‘z’ in the word. Letter ‘i’ in the pattern maps to letter ‘c’ in the word. Letter ‘n’ in the pattern maps to letter ‘z’ in the word. As every letter in the pattern maps uniquely to a corresponding letter in the word. Hence 'zcz' is a valid match.

The very first line of input contains an integer ‘T’ denoting the number of test cases. The first line of every test case contains an integer ‘N’ denoting the number of words present in the list. The second line of every test case contains ‘N’ space-separated strings denoting the words in the list. The third line of every test case contains the pattern string.

For the first test case, the list of words is {cdd, pcm} and the pattern is 'foo'. For the word 'cdd': The letters ‘f’, ‘o’, ‘o’ of the pattern, map to letters ‘c’, ‘d’, ‘d’ of the word respectively. As every letter in the pattern maps uniquely to a corresponding letter in the word. Hence, it is a valid match. For the word 'pcm': The letters ‘f’, ‘o’, ‘o’ of the pattern map to letters ‘p’, ‘c’, ‘m’ of the word respectively. As the same letter ‘o’, in the pattern, maps to two different letters ‘c’ and ‘m’ in the word. Hence, 'pcm' is not a valid match. For the second test case, the list of words is {abcd, km, qst} and the pattern is 'pqr'. For the word 'abcd': The letters ‘p’, ‘q’, ‘r’ of the pattern map to letters ‘a’, ‘b’, ‘c’ of the word respectively. But, there is no character in the pattern which maps to the letter ‘d’ in the word. Hence, it is not a valid match. For the word 'km': The letters ‘p’, ‘q’ of the pattern, map to letters ‘k’, ‘m’ of the word respectively. But. there is no character in the word which maps to the letter ‘r’ in the pattern. Hence, it is not a valid match. For the word 'qst': The letters ‘p’, ‘q’, ‘r’ of the pattern map to letters ‘q’, ‘s’, ‘t’ of the word respectively. As every letter in the pattern maps uniquely to a corresponding letter in the word. Hence, it is a valid match.

Convert Word To String of Integers

The idea is to generate hashes of each word present in the list and compare this hash value with the hash of the pattern string.

Firstly, It should be noted that a word can match the pattern only if the length of the word is equal to the length of the pattern. So, before generating the hash value, we must compare the lengths to check whether they are equal or not to get the answer in ease.
Otherwise, If the hash value of the pattern as well as the word matches, it tells us that the pattern and the word have the same structure i.e. it’s a valid word.

How do we generate a hash for a given word or pattern?

A simple way to generate the hash would be to assign a unique integer to every distinct character in the word (and pattern) one by one, thereby generating a string of integers. This string of integers acts as a hash value for the word (or pattern).
If the hash value of the word matches with the pattern, the word added to the list of valid words. Hence, we can use this check for the similarity between the word and the pattern.

Let us understand this by an example

Let the word be “aabaddeeecf” and the pattern be “ppqpsstttvu”.

Generating the string of integers (hash) for the word:

a -> 1

b -> 2

d -> 3

e -> 4

c -> 5

f -> 6

Hash for the word: 11213344456

Generating the string of integers (hash) for the pattern:

p -> 1

q -> 2

s -> 3

t -> 4

v -> 5

u -> 6

Hash for the pattern: 11213344456

As hashes for word and pattern match each other. Hence, the word is a valid match.

Time Complexity

O(N * length(pattern)), where N is the number of words in the list.

In the worst case, we convert every word (including pattern) to a string of integers that takes the Time Complexity of O(N * length(pattern)). We can optimize it by putting a check if the length of the pattern is equal to the length of the word. Hence, the overall Time Complexity is O(N * length(pattern)).

Space Complexity

O(length(pattern)), where pattern is the given string.

In the worst case, The Space Complexity O( length(pattern)) is required by the HashMap. Hence, the overall Space Complexity is O(length(pattern)).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation 1:

Sample Input 2:

Sample Output 2:

Sample Input 3:

Sample Output 3: