Java Accepted DFS Solution


  • 0
    M
    public class Solution {
        public int minMutation(String start, String end, String[] bank) {
            return minMutation(start, end, bank, new HashSet<>(), 0);
        }
        
        private int minMutation(String start, String end, String[] bank, Set<String> visited, int count) {
            if(start.equals(end)) {
                return count;
            }
            
            int min = Integer.MAX_VALUE;
            for(String validGene : bank) {
                if(!visited.contains(validGene) && isOneEditDistance(validGene, start)) {
                    visited.add(validGene);
                    int ret = minMutation(validGene, end, bank, visited, count + 1);
                    if(ret != -1) {
                        min = Math.min(min, ret);
                    }
                    visited.remove(validGene);
                }
            }
            return min == Integer.MAX_VALUE ? -1 : min;
        }
        
        private boolean isOneEditDistance(String s, String t) {
            for (int i = 0; i < Math.min(s.length(), t.length()); i++) { 
            	if (s.charAt(i) != t.charAt(i)) {
            		if (s.length() == t.length())
            			return s.substring(i + 1).equals(t.substring(i + 1));
        			else if (s.length() < t.length())
        				return s.substring(i).equals(t.substring(i + 1));	        	
        			else
        				return t.substring(i).equals(s.substring(i + 1));
            	}
            }       
            return Math.abs(s.length() - t.length()) == 1;        
        }
    }
    

Log in to reply
 

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