433.Minimum Genetic Mutation

Tags: [BFS], [queue], [map], [set]

Com: {t}

Hard: [##]

Link: https://leetcode.com/problems/minimum-genetic-mutation/#/description

A gene string can be represented by an 8-character long string, with choices from"A","C","G","T".

Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string.

For example,"AACCGGTT"->"AACCGGTA"is 1 mutation.

Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.

Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1.

Note:

1. Starting point is assumed to be valid, so it might not be included in the bank.
2. If multiple mutations are needed, all mutations during in the sequence must be valid.
3. You may assume start and end string is not the same.

Example 1:

start: "AACCGGTT"
end:   "AACCGGTA"
bank: ["AACCGGTA"]

return: 1

Example 2:

start: "AACCGGTT"
end:   "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

return: 2

Example 3:

start: "AAAAACCC"
end:   "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

return: 3

Solution: BFS, Queue, Map

public class Solution {
    public int minMutation(String start, String end, String[] bank) {
        // check input
        if (start == null || start.length() < 8 || end == null || end.length() < 8) {
            throw new IllegalArgumentException("the input is invalid");
        }

        char[] candidates = new char[]{'A', 'C', 'G', 'T'};
        Set<String> genes = new HashSet<>(Arrays.asList(bank));

        // BFS
        Map<String, Integer> distanceMap = new HashMap<>();
        distanceMap.put(start, 0);
        Queue<String> queue = new LinkedList<>();
        queue.add(start);

        while (queue.size() > 0) {
            String curr = queue.remove();
            int distance = distanceMap.get(curr);

            if (curr.equals(end)) {
                return distance;
            }

            char[] chars = curr.toCharArray();
            for (int i = 0; i < 8; i ++) {
                char originalChar = chars[i];

                for (int j = 0; j < candidates.length; j ++) {
                    if (candidates[j] == originalChar) {
                        continue;
                    }
                    chars[i] = candidates[j];
                    String newStr = String.valueOf(chars);
                    if (!genes.contains(newStr) || distanceMap.containsKey(newStr)) {
                        continue;
                    }

                    distanceMap.put(newStr, distance + 1);
                    queue.add(newStr);
                }

                chars[i] = originalChar;
            }
        }

        return -1;
    }
}

Revelation:

• In Java, to check two strings' values are equal or not, we should use 'String.equals(otherString)'.

• In Java, to append the element into queue, using queue.add(), to pop the left element from queue using the queue.popleft().

• In Java, to dump the String[] into Set, we can use Set<String> set = new HashSet<>(Arrays.asList(stringArr)).

• In Java, to convert the String into char array, we can use string.toCharArray().

• In Java, to convert char array into String, we can use String.valueOf(char array).
• In Java, map.get(key), if the key not in the map, the map.get() will return null.

Note:

• Time complexity = O(len(candidates)), because there are len(candiddates) nodes in the graph.

Solution: BFS, Python

class Solution(object):
    def minMutation(self, start, end, bank):
        """
        :type start: str
        :type end: str
        :type bank: List[str]
        :rtype: int
        """
        if not start or len(start) < 8 or not end or len(end) < 8:
            raise ValueError('the input is invalid')

        genes = set(bank)
        candidates = ['A', 'C', 'G', 'T']

        visited = set()
        queue = collections.deque()
        visited.add(start)
        queue.append((start, 0))

        while queue:
            curr, dis = queue.popleft()
            if curr == end:
                return dis

            chars = list(curr)
            for i in xrange(8):
                original_char = chars[i]

                for c in candidates:
                    if c == original_char:
                        continue
                    chars[i] = c
                    new_gene = ''.join(chars)
                    if new_gene not in genes or new_gene in visited:
                        continue

                    visited.add(new_gene)
                    queue.append((new_gene, dis + 1))

                chars[i] = original_char

        return -1