839.Similar String Groups

tags: Hard,Array,String,DFS,BFS

839. Similar String Groups

題目描述

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y. Also two strings X and Y are similar if they are equal.

For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".

Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}. Notice that "tars" and "arts" are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list strs of strings where every string in strs is an anagram of every other string in strs. How many groups are there?

範例

Example 1:

Input: strs = ["tars","rats","arts","star"]
Output: 2

Example 2:

Input: strs = ["omv","ovm"]
Output: 1

Constraints:

• 1 <= strs.length <= 300
• 1 <= strs[i].length <= 300
• strs[i] consists of lowercase letters only.
• All words in strs have the same length and are anagrams of each other.

解答

Python

class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        n = len(strs)
        parents = list(range(n))

        def find(x):
            if parents[x] != x:
                parents[x] = find(parents[x])
            return parents[x]
        
        def union(x, y):
            xr, yr = find(x), find(y)
            if xr != yr:
                parents[xr] = yr
        
        def similar(s1, s2):
            diff = 0
            for c1, c2 in zip(s1, s2):
                if c1 != c2:
                    diff += 1
                if diff > 2:
                    return False
            return diff == 0 or diff == 2
        
        for i, j in combinations(range(n), 2):
            if similar(strs[i], strs[j]):
                union(i, j)
        
        return len(set(find(i) for i in range(n)))

Yen-Chi ChenFri, Apr 28, 2023

ChatGPT

To solve this problem, you can use the Disjoint Set Union (DSU) data structure. It's a data structure that allows you to efficiently group elements into disjoint sets and check which set an element belongs to. Here's a Python implementation to solve the problem:

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        if xr != yr:
            self.parent[xr] = yr

def are_similar(s1, s2):
    diff_count = 0
    for i in range(len(s1)):
        if s1[i] != s2[i]:
            diff_count += 1
        if diff_count > 2:
            return False
    return diff_count == 2 or diff_count == 0

def count_groups(strs):
    n = len(strs)
    dsu = DSU(n)

    for i in range(n):
        for j in range(i + 1, n):
            if are_similar(strs[i], strs[j]):
                dsu.union(i, j)

    return len(set(dsu.find(i) for i in range(n)))

# Example usage
strs = ["tars", "rats", "arts", "star"]
print(count_groups(strs))  # Output: 2

This implementation defines a DSU class with the basic functionality for union and find operations. The are_similar function checks if two strings are similar, and the count_groups function counts the number of groups in the input list of strings using the DSU class.

Reference

回到題目列表