如何使用联合查找数据结构对字符串进行分组？

Question

我一直在使用Union-Find (不相交集合)来解决很多图问题，并且知道它是如何工作的。但我几乎总是将这种数据结构与整数或数字一起使用。在求解this leetcode problem时，我需要对字符串进行分组，我正在考虑使用Union-Find来解决这个问题。但是我不知道如何在字符串中使用它。寻求建议。

Answer 1

TLDR:使用与整数/数字相同的联合查找代码，但使用散列映射而不是数组来存储联合查找中每个元素的父元素。这种方法适用于任何可以存储在散列映射中的数据类型，而不仅仅是字符串，也就是说，在下面的代码中，两个无序映射可以使用字符串或整数以外的其他数据类型作为键。

class UnionFind {
public: 
    string find(string s) { 
        string stringForPathCompression = s; 
        while(parent[s] != s) s = parent[s];
        
        // The following while loop implements what is known as path compression, which reduces the time complexity. 
        while(stringForPathCompression != s) { 
            string temp = parent[stringForPathCompression]; 
            parent[stringForPathCompression] = s; 
            stringForPathCompression = temp; 
        }
        return s; 
    }
    void unify(string s1, string s2) {
        string rootS1 = find(s1), rootS2 = find(s2); 
        if(rootS1 == rootS2) return; 
        
        // we unify the smaller component to the bigger component, thus preserving the bigger component. 
        // this is known as union by size, and reduces the time complexity
        if(sz[rootS1] < sz[rootS2]) parent[rootS1] = rootS2, sz[rootS2] += sz[rootS1]; 
        else parent[rootS2] = rootS1, sz[rootS1] += sz[rootS2];         
    }
private: 
    // If we were storing numbers in our union find, both of the hash maps below could be arrays
    unordered_map<string, int> sz; // aka size.
    unordered_map<string, string> parent; 
};