Word Pattern

Easy
0/40
Average time to solve is 15m
profile
Contributed by
7 upvotes
Asked in companies
UberMaster Card

Problem statement

You have been given two strings 'S' and ‘T’. Your task is to find if ‘S’ follows the same pattern as ‘T’.

Here follow means a full match, i.e. there is a bijection between a letter of ‘T’ and a non-empty word of ‘S’.

For Example: 
If the given string is S = "lion cow cow lion" and T = “wccw”, then the string ‘S’ follows the same pattern as string ‘T’.
Note: 
'T’ contains only lowercase English letters.

‘S’ contains only lowercase English letters and spaces.

‘S’ does not contain any trailing or leading spaces. All words in ‘S’ are separated by a single space.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains a string ‘S’.

The second line of each test case contains a string ‘T’.
Output Format: 
For each test case, the only line of output will print “Yes” if ‘S’ follows the same pattern as ‘T’. Else print “No”.

Print the output of each test case in a separate line.
Note: 
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints: 
1 <= t <= 100
1 <= |S| <= 5000
1 <= |T| <= 5000

Time Limit: 1 second
Sample Input 1:
1
ship ship ship ship
rrbb
Sample Output 1:
No
Explanation For Sample Output 1:
Here, string ‘S’ does not match the pattern with the string ‘T’ because different characters map the same word.
Sample Input 2:
2
red blue blue red
ebbe
moon moon moon moon
aaaa
Sample Output 2:
Yes
Yes
Hint

Try to map the characters of ‘T’ to words of ‘S’ and words of ‘S’ to characters of ‘T’.

Approaches (1)
Hashmap

We will use two hashmaps ‘charToWord’ and ‘wordToChar’ to track which character of ‘T’ maps to which word of ‘S’ and which word of ‘S’ maps to which character of ‘T’,  respectively.

 

Here is the algorithm:

  1. We initialise two hashmaps ‘charToWord’ and ‘wordToChar’.
  2. We scan each character-word pair
    1. If the character is not present in ‘charToWord’ 
      1. If the word is already present in ‘wordToChar’ 
        1. Return “No”. Since it has been mapped with some other character before.
      2. Else
        1. Map the character of ‘T’ to the word of ‘S’.
        2. Map the word of ‘S’ to the character of ‘T’.
    2. Else
      1. If the current word is not equal to the word that character maps to in ‘charToWord’ 
        1. Return “No”.
  3. Finally, return “Yes”.
Time Complexity

O(N),  where ‘N’ represents the number of words in ‘S’ or the number of characters in ‘T’.  

 

Since we are iterating all characters of ‘T’ and all words of ‘S’. Hence, the time complexity is linear. 

Space Complexity

O(1), i.e. constant space complexity.

 

Even though we have used two hashmaps, the size of both hashmaps does not exceed 26. Hence, the space complexity is constant.

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