Identical sentences

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’.

After constructing a graph with the ‘pairs’ array as an edge, the problem reduces to finding if the node with ‘word2[i]’ is reachable from the node with ‘word2[i]’, i.e., to check if both these nodes belong to the same connected component.

Connected component: A subgraph in which each pair of nodes is connected via a path.

We can find the connected components by performing a DFS (or BFS) traversal starting from every unvisited node. Each DFS traversal will mark each node in a single connected component as visited. Here, the visited array will store the component number of each node. If two nodes have the same component number (they belong to the same component), they are connected through a path. 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]’.
• Set ‘num = 1’. Use it to mark each node with its corresponding component number.
• Create a hash map ‘comp’ that maps strings to integers. Use it to keep track of visited nodes in the DFS traversal and store each node’s component number.
• Run a loop where ‘i’ ranges from 0 to ‘n-1’:
  • If ‘word1[i]’ is not present in ‘comp’, then:
    • Call the function ‘dfs(word1[i], num)’. Mark all nodes that are reachable from ‘word1[i]’ into ‘comp’ with the value ‘num’.
    • ‘compNum += 1’
• Run a loop where ‘i’ ranges from 0 to ‘n’:
  • ‘u = word1[i]’ and ‘v = word2[i]’.
  • If (‘u’ is not equal to ‘v’) and (‘comp[u]’ is not equal to ‘comp[v]’), then ‘u’ is not reachable from ‘v’:
    • Return false as the answer.
• Return true for the answer (All words in ‘word1’ and ‘word2’ are identical).

The ‘dfs(string s1, integer num)’ function:

• Add ‘(s1, num)’ into ‘comp’.
• Run a loop where ‘i’ ranges from 0 to ‘length(graph[s1])’:
  • If ‘graph[s1][i]’ is not present in ‘comp’ then we have not visited this word:
    • Call the function ‘dfs(graph[s1][i], num)’.

Disjoint-set (or Union-find) is a data structure that stores a collection of disjoint (non-overlapping) sets. This data structure consists of three basic operations:

• makeSet(v): Create a new set containing the element ‘v’.
• unionSet(a, b): Merge the two specified sets, the set containing element ‘a’ and the set containing element ‘b’.
• findSet(v): Return the representative (also called leader) of the set containing the element ‘v’.

The idea is to use a Disjoint-set ‘ds’ to store all nodes in a connected component into a single set. If two nodes are in the same set, they are identical (as they are reachable from one another). Following is the implementation:

• If ‘n’ is not equal to ‘m’, then return false.
• Initialize the Disjoint-set ‘ds’ with ‘2*p+1’ sets. In the worst-case, ‘pairs’ can have ‘2*p’ different string.
• Create a hash map ‘words’ that maps strings to integers.
• Map each string in ‘pairs’ to a unique integer, starting from ‘1’ (this will allow us to use the Disjoint-set data structure’s standard template).
• Set ‘id = 1’
• Run a loop where ‘i’ ranges from ‘0’ to ‘p-1’:
  • If ‘pairs[i][0]’ is not present in ‘words’, then:
    • Insert ‘(pairs[i][0], id)’ into ‘words’
    • ‘id += 1’
  • If ‘pairs[i][1]’ is not present in ‘words’, then:
    • Insert ‘(pairs[i][1], id)’ into ‘words’
    • ‘id += 1’
  • ‘u = words[pairs[i][0]]’ and ‘v = words[pairs[i][1]]’
  • ‘ds.unionSet(u, v)’. We merge the sets containing the words ‘u’ and ‘v’, as each node reachable from ‘u’ is also reachable from ‘v’ and vice-versa.
• Run a loop where ‘i’ ranges from ‘0’ to ‘n-1’:
  • ‘u = word1[i]’ and ‘v = word2[i]’.
  • If ‘u = v’, then the strings are identical:
    • Continue to the next loop iteration.
  • If (‘u’ or ‘v’ is not present in ‘words’) or (‘ds.findSet(words[u]) != ds.findSet(words[v])’), then the strings are not identical:
    • Return false as the answer.
• Return true as the answer.