Identical sentences

Hard
0/120
Average time to solve is 40m
profile
Contributed by
7 upvotes
Asked in companies
UberVisaExpedia Group

Problem statement

You are given two sentences, ‘word1’ and ‘word2’, represented as an array of strings of size ‘n’ and ‘m’, respectively. You are also given an array called ‘pairs’. Each element in ‘pairs’ is of the form ‘[u, v]’ where ‘u’ and ‘v’ are strings.

Properties of the array ‘pairs’:

  1. If ‘[u, v]’ or ‘[v, u]’ is present in ‘pairs’, then the words (or strings) ‘u’ and ‘v’ are identical.
  2. If ‘u’ and ‘x’ are identical, and ‘v’ and ‘x’ are identical, then the words ‘u’ and ‘v’ are identical.
  3. Every word is identical to itself, i.e., the word ‘u’ and ‘u’ are always identical.

For two sentences, ‘word1’ and ‘word2’ to be identical:

  1. For every word (‘word1[i]’) in ‘word1’, the words ‘word1[i]’ and ‘word2[i]’ must be identical.
  2. ‘word1’ and ‘word2’ must have the same number of words.

Using the array ‘pairs’, you have to determine if ‘word1’ and ‘word2’ are identical.

Example : 
‘word1’ = [“exceptional”, “coding”, “skills”]
‘word2’ = [“great”, “coding”, “talent”]
‘pairs’ = [ [“exceptional”, “good”], [“great”, “good”], [“skills”, “talent”] ]

For each word in ‘word1’, we have:
1. “exceptional” = “great”, because “exceptional” = “good” and “good” = “great”
2. “coding” = “coding”, as every word is identical to itself.
3. “skills” = “talent”, because [“skills”, “talent”] is present in ‘pairs’.

As every word in ‘word1’ is identical to the corresponding word in ‘word2’, the given sentences are identical.
Note : 
1. The array ‘pairs’ can have words that are not present in ‘word1’ and ‘word2’.
2. Each pair ‘[u, v]’ in ‘pairs’ is unique, and if a pair ‘[u, v]’ is present, then there will never be a pair ‘[v, u]’.
3. You do not need to print anything; it has already been taken care of. Just implement the function.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line of each test case contains three integers, ‘n’, ‘m’, and ‘p’ denoting the number of elements in array ‘word1’, ‘word2’, and ‘pairs’.

The second line of each test case contains ‘n’ space-separated words denoting ‘word1’.

The third line of each test case contains ‘m’ space-separated words denoting ‘word2’.

The following ‘p’ lines of each test case contain two space-separated words denoting an element in ‘pairs’.

For more clarity, please refer to the sample inputs.
Output format: 
For every test case, return true if the sentences ‘word1’ and ‘word2’ are identical, else return false.
Constraints: 
1 <= T <= 1
1 <= n, m <= 1000
0 <= p <= 2000
Each element of ‘pairs’ contains exactly two words.
Length of each word in ‘word1’, ‘word2’ and ‘pairs[i]’ is in the range [1, 20].
Value of each word in ‘word1’, ‘word2’ and ‘pairs[i]’ varies from [a, z].

Where ‘T’ is the number of test cases, ‘n’ is the number of words in ‘word1’, ‘m’ is the number of words in ‘word2’, and ‘p’ is the number of elements in ‘pairs’.

Time limit: 1 second

Sample input 1 :

2
2 2 4
better life
fine country  
better good
fine great
great good
life fine
3 3 1
this is it
that is it
that this

Sample output 1 :

False
True

Explanation of sample input 1 :

Test Case 1:
‘word1’ = [“better”, “life”]
‘word2’ = [“fine”, “country”]
‘pairs’ = [ [“better”, “good”], [“fine”, “great”], [“great”, “good”], [“life”, “fine” ] ]

For each word in ‘word1’, we have:
1. “better” = “fine”, because “better” = “good”, “good” = “great” and “great” = “fine”.
2. “life” is not identical to “country”.

As the last word in ‘word1’ is not identical to the last word in ‘word2’, the given sentences are not identical.

Test Case 2:
‘word1’ = [“this”, “is”, “it]
‘word2’ = [“that”, “is”, “it”]
‘pairs’ = [ [“that”, “this”] ]

For each word in ‘word1’, we have:
1. “this” = “that”, because [“that”, “this”] is present in ‘pairs’.
2. “is” = “is”, as every word is identical to itself.
3. “it” = “it”, as every word is identical to itself.

As every word in ‘word1’ is identical to the corresponding word in ‘word2’, the given sentences are identical.

Sample input 2 :

2
3 3 0
sample input one
sample input one
4 4 3
this too shall pass
that one must pass
this that
one two
two too

Sample output 2 :

True
False
Hint

Consider each element in ‘pairs’ as an edge of a graph.

Approaches (3)
Using DFS

Consider each element ‘[u, v]’ in ‘pairs’ as an edge of an undirected graph (as ‘[u, v]’ and ‘[v, u]’ are the same). If a node ‘v’ is reachable from a node ‘u’, then the string ‘u’ and ‘v’ are identical. Now, traverse the graph using DFS (or BFS) traversal starting from ‘word1[i]’, and if we can reach the node ‘word2[i]’ then ‘word1[i]’ and ‘word2[i]’ are identical. Following is a solution using DFS traversal:

 

  • If ‘n’ is not equal to ‘m’, then return false.
  • Create a hash map ‘graph’ that maps strings to a list of strings. Use ‘graph[str]’ to store the nodes connected to string ‘str’.
  • Run a loop where ‘i’ ranges from 0 to ‘p-1’ and create an edge in ‘graph’ for each element in ‘pairs’:
    • ‘u = pairs[i][0]’ and ‘v = pairs[i][1]’.
    • Insert the string ‘u’ into ‘graph[v]’.
    • Insert the string ‘v’ into ‘graph[u]’.
  • Run a loop where ‘i’ ranges from 0 to ‘n-1’:
    • If ‘word1[i] = word2[i]’, then the two strings are identical:
      • Continue the loop from next iteration.
    • Create a hash map ‘visited’. It’s used to keep track of visited nodes in the DFS traversal.
    • If ‘dfs(word1[i], word2[i])’ is false, the two strings are not identical:
      • Return false for the answer.
  • Return true for the answer (All words in ‘word1’ and ‘word2’ are identical).

 

The ‘dfs(string s1, string s2)’ function:

  • Add the string ‘s1’ into ‘visited’.
  • Run a loop where ‘i’ ranges from 0 to ‘length(graph[s1])’:
    • If ‘graph[s1][i] = s2’, then the strings are identical:
      • Return true.
    • If we have not visited ‘graph[s1][i]’ and ‘dfs(graph[s1][i], s2)’ is true, then:
      • Return true.
  • Return false, as we have not found the string ‘s2’.
Time Complexity

O(n*p), where ‘n’ is the number of words in ‘word1’ and ‘p’ is the number of elements in the array ‘pairs’.

 

In the worst-case scenario, every DFS call traverses the entire graph (visiting every edge). So, for ‘n’ such calls, the time complexity becomes ‘O(n*p)’.

Space Complexity

O(p),  ‘p’ is the number of elements in the array ‘pairs’.

 

Since there are ‘p’ edges, we require ‘O(p)’ space to store the graph. The maximum size of the recursive stack used in DFS will be equal to the number of elements in the graph which is ‘O(p)’ (as ‘pairs’ can have strings that are not present in ‘word1’ and ‘word2’).

Code Solution
(100% EXP penalty)
Identical sentences
Full screen
Console