Determining Word Equivalence between Arrays
Given two arrays A[] and B[] of strings and an array of pairs[] where each pair of words is equivalent and also follows transitive property (i.e. if x=y and y=z then x=z), determine whether each ith word of string A is equivalent to ith word of string B.
Examples:
Input: A = [“blue”, “sky”, “is”], B = [“pink”, “sky”, “of”], pairs = [[“blue”, “hi”],[“pink”, “hi”],[“is”, “of”]]
Output: Yes
Explanation: blue = “hi” and “pink” = “hi” so, “blue” = “pink” and “is” = “of” A = BInput: A = [“blue”, “is”], B = [“pink”, “sky”], pairs = [[“pink”, “blue”], [“is”, “for”]]
Output: No
Explanation: pink= “blue” but “is” != “sky” so, A != B so, no
Approach: To solve the problem follow the below idea:
The approach to solve this problem is to use the concept of Disjoint Set Union (DSU), also known as Union-Find.
Below is the code explanation to solve the problem:
- We are using an unordered_map parent to represent relationships between words in the pairs.
- The find function is a recursive function that finds the root of a word. If a word is not found in the parent map, it is considered its own root.
- The unionWords function unions two words into the same set by updating their parent pointers. If the root of x is different from the root of y, x becomes the parent of y, connecting them in the same set.
- In the areEquivalentWords function, it first checks if the sizes of arrays A[] and B[] are equal. If not, it returns “No” because arrays of different lengths cannot be equivalent.
- It then iterates through the given pairs and uses unionWords to build equivalence sets.
- Finally, it checks if the corresponding words in arrays A[] and B[] have the same root (representative). If they don’t, it returns “No.” Otherwise, it returns “Yes.”
Below is the C++ implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; unordered_map<string, string> parent; // Find Fuction of DSU string find(string x) { if (parent.find(x) == parent.end()) return x; return parent[x] = find(parent[x]); } // Union Fuction of DSU void unionWords(string x, string y) { // Find the root of x and y string rootX = find(x); string rootY = find(y); // If their roots are not equal // perform union operation if (rootX != rootY) parent[rootX] = rootY; } // Fuction to tell wether A and B // are equal or not string areEquivalentWords(vector<string>& A, vector<string>& B, vector<vector<string> >& pairs) { // Different lengths, cannot be // equivalent if (A.size() != B.size()) return "no"; for ( auto & pair : pairs) { unionWords(pair[0], pair[1]); } for ( int i = 0; i < A.size(); i++) { if (find(A[i]) != find(B[i])) return "no"; } return "yes"; } // Drivers code int main() { // Input vector of string A vector<string> A = { "blue", "sky", "is" }; // Input vector of string A vector<string> B = { "pink", "sky", "of" }; // Input vector of pairs vector<vector<string> > pairs = { { "blue", "hi" }, { "pink", "hi" }, { "is", "of" } }; // Fuction Call string result = areEquivalentWords(A, B, pairs); cout << result << endl; return 0; } |
Java
import java.util.HashMap; import java.util.Map; public class Main { static Map<String, String> parent = new HashMap<>(); // Find Function of DSU static String find(String x) { if (!parent.containsKey(x)) { return x; } parent.put(x, find(parent.get(x))); return parent.get(x); } // Union Function of DSU static void unionWords(String x, String y) { // Find the root of x and y String rootX = find(x); String rootY = find(y); // If their roots are not equal, perform union operation if (!rootX.equals(rootY)) { parent.put(rootX, rootY); } } // Function to check whether A and B are equivalent or not static String areEquivalentWords(String[] A, String[] B, String[][] pairs) { // Different lengths, cannot be equivalent if (A.length != B.length) { return "no" ; } for (String[] pair : pairs) { unionWords(pair[ 0 ], pair[ 1 ]); } for ( int i = 0 ; i < A.length; i++) { if (!find(A[i]).equals(find(B[i]))){ return "no" ; } } return "yes" ; } // Main function public static void main(String[] args) { // Input array of strings A String[] A = { "blue" , "sky" , "is" }; // Input array of strings B String[] B = { "pink" , "sky" , "of" }; // Input array of pairs String[][] pairs = {{ "blue" , "hi" }, { "pink" , "hi" }, { "is" , "of" }}; // Function Call String result = areEquivalentWords(A, B, pairs); System.out.println(result); } } |
Python3
class DSU: def __init__( self ): self .parent = {} # Initialize a dictionary to store parent-child relationships def find( self , x): if x not in self .parent: return x # If x is not in the parent dictionary, it is its own parent (represents a set) self .parent[x] = self .find( self .parent[x]) # Path compression: make x point directly to the root return self .parent[x] def union( self , x, y): rootX = self .find(x) # Find the root of the set containing x rootY = self .find(y) # Find the root of the set containing y if rootX ! = rootY: self .parent[rootX] = rootY # Connect the root of one set to the root of the other set def are_equivalent_words(A, B, pairs): if len (A) ! = len (B): return "no" # If the lengths of A and B are different, they can't be equivalent dsu = DSU() # Create an instance of the DSU (Disjoint Set Union) class for pair in pairs: dsu.union(pair[ 0 ], pair[ 1 ]) # Union the words in the pairs, connecting their sets for i in range ( len (A)): if dsu.find(A[i]) ! = dsu.find(B[i]): return "no" # If the root of the set containing A[i] is not the same as B[i], they are not equivalent return "yes" # All corresponding words in A and B are equivalent if __name__ = = "__main__" : A = [ "blue" , "sky" , "is" ] B = [ "pink" , "sky" , "of" ] pairs = [[ "blue" , "hi" ], [ "pink" , "hi" ], [ "is" , "of" ]] result = are_equivalent_words(A, B, pairs) # Check if A and B are equivalent using the pairs print (result) # Print the result ("yes" or "no") |
C#
// C# code for the above approach using System; using System.Collections.Generic; public class GFG { static Dictionary< string , string > parent = new Dictionary< string , string >(); // Find Function of DSU static string Find( string x) { if (!parent.ContainsKey(x)) return x; return parent[x] = Find(parent[x]); } // Union Function of DSU static void UnionWords( string x, string y) { // Find the root of x and y string rootX = Find(x); string rootY = Find(y); // If their roots are not equal // perform union operation if (rootX != rootY) parent[rootX] = rootY; } // Function to tell whether A and B // are equivalent or not static string AreEquivalentWords(List< string > A, List< string > B, List<List< string > > pairs) { // Different lengths, cannot be equivalent if (A.Count != B.Count) return "no" ; foreach ( var pair in pairs) { UnionWords(pair[0], pair[1]); } for ( int i = 0; i < A.Count; i++) { if (Find(A[i]) != Find(B[i])) return "no" ; } return "yes" ; } // Drivers code public static void Main( string [] args) { // Input list of string A List< string > A = new List< string >{ "blue" , "sky" , "is" }; // Input list of string B List< string > B = new List< string >{ "pink" , "sky" , "of" }; // Input list of pairs List<List< string > > pairs = new List<List< string > >{ new List< string >{ "blue" , "hi" }, new List< string >{ "pink" , "hi" }, new List< string >{ "is" , "of" } }; // Function Call string result = AreEquivalentWords(A, B, pairs); Console.WriteLine(result); } } // This code is contributed by Susobhan Akhuli |
Javascript
let parent = new Map(); // Find Function of DSU function find(x) { if (!parent.has(x)) return x; return parent.set(x, find(parent.get(x))).get(x); } // Union Function of DSU function unionWords(x, y) { // Find the root of x and y let rootX = find(x); let rootY = find(y); // If their roots are not equal // perform union operation if (rootX !== rootY) parent.set(rootX, rootY); } // Function to tell whether A and B // are equal or not function areEquivalentWords(A, B, pairs) { // Different lengths, cannot be equivalent if (A.length !== B.length) return "no" ; for (let pair of pairs) { unionWords(pair[0], pair[1]); } for (let i = 0; i < A.length; i++) { if (find(A[i]) !== find(B[i])) return "no" ; } return "yes" ; } // Drivers code function main() { // Input array of string A let A = [ "blue" , "sky" , "is" ]; // Input array of string B let B = [ "pink" , "sky" , "of" ]; // Input array of pairs let pairs = [[ "blue" , "hi" ], [ "pink" , "hi" ], [ "is" , "of" ]]; // Function Call let result = areEquivalentWords(A, B, pairs); console.log(result); } // Run the main function main(); |
yes
Time Complexity: O(N*M*log(N)), where N = length of vector A and M is the length of strings.
Auxiliary Space: O(N*M)
Contact Us