Problem statement

https://binarysearch.com/problems/Gene-Mutation-Groups/

Solution

We need to create graph of connection first: we use trick with # symbol. Then run dfs.

Complexity

We have n nodes, then we have n*k elements in graph G. Time complexity can be estimated as O(n*k^2). Space is O(n*k).

Code

class Solution:
    def solve(self, genes):
        n, k = len(genes), len(genes[0])
        G = defaultdict(list)
        G2 = defaultdict(list)
        for g in genes:
            for i in range(k):
                G[g[:i] + "#" + g[i+1:]] += [g]

        for g in G:
            for x, y in zip(G[g], G[g][1:]):
                G2[x] += [y]
                G2[y] += [x]

        comp, V = 0, set()
        
        def dfs(x):
            if x in V: return
            V.add(x)
            for i in G2[x]:
                dfs(i)
        
        for i in range(n):
            if genes[i] not in V:
                dfs(genes[i])
                comp += 1

        return comp

Remark

Similar to Leetcode 0127. Word Ladder