Java BFS & DFS solutions


  • 0
    F

    Let's begin with this very simple-minded idea for solving the problem:

    1. Check if the target gene "end" is in the gene bank. If not, there will be no mutation that can take us from the initial gene to the target gene, so return -1. Otherwise go to next step.

    2. Starting from the initial gene "start", check if it is the same as the target gene "end". If it is, no mutation is needed so return 0. Else go to step 3.

    3. Find all genes in the gene bank that can be obtained by ONE mutation from the initial gene. Check if any of them is the same as the target gene. If there is one, return 1 since we found the target gene by 1 mutation from the initial gene. If none of them is the target gene, repeat step 3 for all genes obtained in this step, i.e., find all genes in the bank that are obtainable by ONE mutation from each of the gene obtained in this step and check if any of them is the target gene. We continue in this fashion until either the target gene is found or confirmed that there is actually no such mutation between the initial and target gene.

    Now let's take a closer look at the steps laid out above. From a structural point of view, all genes (the initial gene, all genes obtained by ONE mutation from it, the "next level" ONE mutation genes, ...) involved in the searching process form a directed graph. Our original problem can be summarized as:

    1. Determine if the target gene is contained in the graph;
    2. If so, find the minimum path length from the initial gene to the target gene.

    Once we've reformulated the problem as searching in a directed graph, I'm sure words like "DFS" or "BFS" will pop into your mind (though the steps above suggest a "BFS" approach). To make our searching process smoother, here are some tips:

    a. To avoid repetition (or cycles in the graph), a gene will be removed from the bank once it is visited. For "DFS", the searching result for each gene should also be memorized.

    b. For java programmers, to set you free from the awkward handling of "mutation" strings, try to encode each gene into an integer (see details below).

    c. It is possible to set up a two-way searching to further speed it up. You may give it a shot if interested.

    For tip b, here is the scheme I took.

    1. First encode each gene character. From the binary representation of each character, the last three bits is good enough to distinguish them.
      'A' = 65 = 01000001 ==> '001' = 1
      'C' = 67 = 01000011 ==> '011' = 3
      'G' = 71 = 01000111 ==> '111' = 7
      'T' = 84 = 01010100 ==> '100' = 4

    2. Encode each gene string. Assume the encoded integer is "igene" (initialized to 0). Starting from the first character in the gene string, fill its corresponding three bits into the three least significant bits of "igene" then shift "igene" to the left by three bits. Continue to the next character in the gene string until it is done. (Note this scheme works as long as the total number of characters in each gene string is no more than 10 for integer type and 21 for long type.)

    3. To obtain all the ONE mutation genes from current gene (encoded as "igene"), simply modify the corresponding bits in "igene" using appropriate bitwise operations.

    All right, putting everything together, here are the "BFS" and "DFS" solutions. For space and time complexity, correct me if I was wrong. Space complexity is O(n) where n is the total number genes in the bank. Time complexity is also O(n) since each gene in the bank will be visited only once.

    1. "BFS" solution:
    int[] keys = {1, 3, 4, 7};
        
    public int minMutation(String start, String end, String[] bank) {
        int istart = 0, iend = 0, res = 0;
        Set<Integer> set = new HashSet<>(bank.length);
            
        for (char c : start.toCharArray()) istart = (istart << 3) | (c & 7);
        for (char c : end.toCharArray()) iend = (iend << 3) | (c & 7);
            
        for (String gene : bank) {
            int igene = 0;
            for (char c : gene.toCharArray()) igene = (igene << 3) | (c & 7);
            set.add(igene);
        }
            
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offerLast(istart);
            
        while (!queue.isEmpty()) {
            int size = queue.size();
            	
            for (int i = 0; i < size; i++) {
                int curr = queue.pollFirst();
                if (curr == iend) return res;
                set.remove(curr);
            		
                for (int j = 0; j < 24; j += 3) {
                    int base = curr & ~(7 << j);
                        
                    for (int k : keys) {
                        int next = base | (k << j);
                        if (set.contains(next)) queue.offerLast(next);
                    }
                }
            }
            	
            res++;
        }
            
        return -1;
    }
    
    1. "DFS" solution:
    int[] keys = {1, 3, 4, 7};
        
    public int minMutation(String start, String end, String[] bank) {
        int istart = 0, iend = 0;
        Set<Integer> set = new HashSet<>(bank.length);
            
        for (char c : start.toCharArray()) istart = (istart << 3) | (c & 7);
        for (char c : end.toCharArray()) iend = (iend << 3) | (c & 7);
                
        for (String gene : bank) {
            int igene = 0;
            for (char c : gene.toCharArray()) igene = (igene << 3) | (c & 7);
            set.add(igene);
        }
            
        if (!set.contains(iend)) return -1;
            
        Map<Integer, Integer> map = new HashMap<>();
        map.put(iend, 0);
            
        return minMutation(istart, map, set);
    }
        
    private int minMutation(int curr, Map<Integer, Integer> map, Set<Integer> set) {
        if (map.containsKey(curr)) return map.get(curr);
            
        int res = -1;
        set.remove(curr);
            
        for (int i = 0; i < 24; i += 3) {
            int base = curr & ~(7 << i);
                
            for (int k : keys) {
                int next = base | (k << i);
                    
                if (set.contains(next)) {
                    int r = 1 + minMutation(next, map, set);
                    if (r > 0) res = (res == -1 ? r : Math.min(res, r));
                }
            }
        }
            
        map.put(curr, res);
        return res;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.