Java Solution with BFS on Graph; Easy to understand


  • 0
    Y

    First, create a graph with string bank. there is a connection b/w strings if their distance is 1
    Second, start from the start string, search the graph with BFS to get the end string

    public class Solution {
        public int minMutation(String start, String end, String[] bank) {
            Set<String> set = new HashSet<>();
            
            for (int i = 0; i < bank.length; i++)
                set.add(bank[i]);
            set.add(start);
            
            if (!set.contains(end))
                return -1;
            
            HashMap<String, Set<String>> map = new HashMap<>();
            for (String s : set) {
                map.put(s, new HashSet<String>());
                for (String t : set) {
                    if (distance(s, t) == 1)
                        map.get(s).add(t);
                }
            }
            
            int count = 1;
            Queue<String> queue = new LinkedList<>();
            
            queue.addAll(map.get(start));
            
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    String cur = queue.poll();
                    if (cur.equals(end))
                        return count;
                    for (String next : map.get(cur)) {
                        if (set.contains(next)) {
                            queue.offer(next);
                            set.remove(next);
                        }
                    }
                }
                count++;
            }
            return -1;
        }
        private int distance(String s, String t) {
            if (s.length() != t.length())
                return -1;
                
            int count = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) != t.charAt(i)) {
                    count++;
                    if (count > 1)
                        return -1;
                }
            }
            return count;
        }
    }
    

Log in to reply
 

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