Teaching Kids Programming – Find Gene Mutation Groups via Breadth First Search Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of unique strings genes where each element has the same length and contains characters “A”, “C”, “G” and/or “T”.

If strings a and b are the same string except for one character, then a and b are in the same mutation group.
If strings a and b are in a group and b and c are in a group, then a and c are in the same group.
Return the total number of mutation groups.

Constraints
n ≤ 10,000
k ≤ 20 where k is the length of a string in genes
Example 1
Input
genes = [“ACGT”, “ACCT”, “AGGT”, “TTTT”, “TTTG”]
Output
2
Explanation
There are two mutation groups:
[“ACGT”, “ACCT”, “AGGT”]
[“TTTT”, “TTTG”]

Hint:
How can we connect one word with another? Is there a better way to connect than simply comparing each pair? After connecting words with each other, return the groups they form.

Gene Mutation Groups via Recursive Breadth First Search Algorithm

Instead of performing a Depth First Search Algorithm, we can do a Breadth First Search Algorithm on each unvisited vertex. Our target is to mark all connected vertices (the genes) in the Graph at one go and then increment the counter which is the number of connected components.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def geneMutationGroup(self, genes):        
        g = set(genes)
 
        def bfs(a):
            q = deque([a])
            while q:
                cur = q.popleft()
                for i in range(len(cur)):
                    for x in ('A', 'C', 'G', 'T'):
                        n = cur[:i] + x + cur[i+1:]
                        if n in g:
                            g.remove(n)
                            q.append(n)
                            
        ans = 0
        for i in genes:
            if i in g:
                ans += 1
                bfs(i)
 
        return ans

class Solution:
    def geneMutationGroup(self, genes):        
        g = set(genes)

        def bfs(a):
            q = deque([a])
            while q:
                cur = q.popleft()
                for i in range(len(cur)):
                    for x in ('A', 'C', 'G', 'T'):
                        n = cur[:i] + x + cur[i+1:]
                        if n in g:
                            g.remove(n)
                            q.append(n)
                            
        ans = 0
        for i in genes:
            if i in g:
                ans += 1
                bfs(i)

        return ans

Finding the edges are similar to what we have done in Recursive Depth First Search implementation. We try to replace each gene with a mutation which differs by only one letter. Then we remove it from the unvisited set and append it to the queue.

See also – traversing a Graph can also be done in Depth First Search Algorithm: Teaching Kids Programming – Find Gene Mutation Groups via Depth First Search Algorithm

Find Gene Mutation Groups

• Teaching Kids Programming – Find Gene Mutation Groups via UnionFind Algorithm (Disjoint Set)
• Teaching Kids Programming – Find Gene Mutation Groups via Breadth First Search Algorithm
• Teaching Kids Programming – Find Gene Mutation Groups via Recursive Depth First Search Algorithm

–EOF (The Ultimate Computing & Technology Blog) —