Java Solution using BFS


  • 13
    public class Solution {
        public int minMutation(String start, String end, String[] bank) {
            if(start.equals(end)) return 0;
            
            Set<String> bankSet = new HashSet<>();
            for(String b: bank) bankSet.add(b);
            
            char[] charSet = new char[]{'A', 'C', 'G', 'T'};
            
            int level = 0;
            Set<String> visited = new HashSet<>();
            Queue<String> queue = new LinkedList<>();
            queue.offer(start);
            visited.add(start);
            
            while(!queue.isEmpty()) {
                int size = queue.size();
                while(size-- > 0) {
                    String curr = queue.poll();
                    if(curr.equals(end)) return level;
                    
                    char[] currArray = curr.toCharArray();
                    for(int i = 0; i < currArray.length; i++) {
                        char old = currArray[i];
                        for(char c: charSet) {
                            currArray[i] = c;
                            String next = new String(currArray);
                            if(!visited.contains(next) && bankSet.contains(next)) {
                                visited.add(next);
                                queue.offer(next);
                            }
                        }
                        currArray[i] = old;
                    }
                }
                level++;
            }
            return -1;
        }
    }
    

  • -2
    U
    This post is deleted!

  • 0
    J
    This post is deleted!

  • 1
    J

    What is the runtime for this in time and space?


  • 0
    M

    I arrived at a very similar solution except this can be slightly speedier if you test for 'end' when you generate new candidates. My solution solves all tests in 3ms.

        public int minMutation(String start, String end, String[] b) {
            char[] AGCT = {'A', 'G', 'C', 'T'};
            Set<String> closed = new HashSet<>();
            Set<String> bank = new HashSet<>();
            for (String s : b) bank.add(s);
            Queue<String> open = new LinkedList<>();
            open.offer(start);
            int depth = 0;
            
            while (!open.isEmpty()) {
                Queue<String> layer = open; 
                open = new LinkedList<>();
                while (!layer.isEmpty()) {
                    String next = layer.poll();
                    closed.add(next);
                    char[] chars = next.toCharArray();
                    for (int i=0; i<chars.length; i++) {
                        char c = chars[i];
                        for (char n : AGCT) {
                            if (c != n) {
                                chars[i] = n;
                                String s = new String(chars);
                                if (!closed.contains(s) && bank.contains(s)) {
                                    if (s.equals(end)) {
                                        return depth+1;
                                    }
                                    open.offer(s);
                                }
                            }
                        }
                        chars[i] = c;
                    }
                }
                depth++;
            }
            return -1;
        }

  • 0

    brilliant solution.


  • 0
    K

    Thanks for the nice solution!!

    I have a question about time complexity.

    I thought time complexity was O(N * N * M * K) where:

    • N is length of start string
    • M is number of letters in gene
    • K is number of strings in bank

    My thinking ways were:

    • We are generating mutations by changing each letter in start string. Then, We will have O(N * M) mutations.
    • Generating a mutation takes O(N) because of toCharArray() and new String()
    • We will add at most O(K) mutations into queue and there is no duplicate because of set

    What do you think about time complexity?


Log in to reply
 

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