Java 2ms BackTracking solution.


  • 3
    1

    Hi all,
    I tried to solve this problem using backtracking as an exercise.
    What do you think?

    public class Solution {
        public int minMutation(String start, String end, String[] bank) {
            if(start.length()!=end.length()) return -1;
            if(start==end) return 0;
            
            Set<String> set = new HashSet<>();
            
            int min = Integer.MAX_VALUE;
            for(String s: bank){
                if(dist(start,s)>1) continue;
                set.add(s);
                min = Math.min(min, minMutation(s,end,bank,set,0));
                set.remove(s);
            }
            
            if(min==Integer.MAX_VALUE) return -1;
            return min;
        }
        
        public int minMutation(String current, String end, String[] bank, Set<String> set, int depth){
            if(current.equals(end)) return 1;
            int min = Integer.MAX_VALUE;
            
            if(depth>=end.length()) return min;
            
            for(String s: bank){
                int diff=dist(current,s);
                if(!set.contains(s) && (diff==1)){
                    set.add(s);
                    int num = minMutation(s,end,bank,set,depth+1);
                    min = Math.min(min, num);
                    set.remove(s);
                }
            }
            if(min==Integer.MAX_VALUE)
                return min;
            return 1+min;
        }
        
        // counts the distance between two strings
        public int dist(String start, String end){
            if(start.length()!=end.length()) return Integer.MAX_VALUE;
            int diff = 0;
            for(int i=0; i<start.length(); i++){
                if(start.charAt(i)!=end.charAt(i)) diff++;
            }
            return diff;
        }
    } 
    

  • 1
    L

    @15daniel10 I improved a little bit based on your solution. See detail below:

    public class RefMinimumGeneticMutation implements Solution {
        public int minMutation(String start, String end, String[] bank) {
            if (start == null || end == null || bank == null || bank.length == 0 || start.length() != end.length())
                return -1;
            if (start.equals(end)) return 0;
            return minMutation(start, end, bank, new HashSet<String>(), 0);
        }
    
        private int minMutation(String current, String end, String[] bank, Set<String> path, int depth) {
            int min = -1;
            if (current.equals(end)) return 0;
            if (depth >= end.length()) return min;
            for (String gene : bank) {
                if (!path.contains(gene) && isClose(current, gene)) {
                    path.add(gene);
                    int num = minMutation(gene, end, bank, path, depth++);
                    if (num != -1) 
                        min =  Math.min(Integer.MAX_VALUE, num + 1);
                    path.remove(gene);
                }
            }
            return min;
        }
    
        //check dist is ONE
        private boolean isClose(String a, String b) {
            if (a.length() != b.length()) return false;
            for (int i = 0, diffs=0; i < a.length(); i++) {
                if (a.charAt(i) != b.charAt(i) && ++diffs > 1) return false;
            }
            return true;
        }
    }
    

  • 0
    1

    @laqxs that's nice!
    You removed a lot of duplicated code that I wrote:)

    But, I think you maybe have a small 'problem' at you're solution.
    min = Math.min(Integer.MAX_VALUE, num + 1) will never return MAX_VALUE I think.
    In my solution, I added the MAX_VALUE to check if there is any problem inside the recursion.. I think you just worked around it and don't really need to use it at all..

    Am I right?


  • 0
    L

    @15daniel10 Yes, my solution does not return MAX_VALUE. It either return -1 directly or actual min mutations. That's another change I made according to your solution :)


  • 0
    1

    @laqxs so here:

    if (num != -1) 
              min =  Math.min(Integer.MAX_VALUE, num + 1);
    path.remove(gene);
    

    you can just assign min to num+1 :)


  • 0
    L

    @15daniel10 Yes, it works. I forgot that the code already checked if (num!=-1).


  • 0
    S

    If there were two possible paths from the start string to the end string, and one path was longer than the other, wouldn't this return the longer sub-optimal path if it was encountered first?


Log in to reply
 

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