BFS - Solution

The point is not to scare this looked complicated question… analyze it… process queue, and a map for record processed… not hard at all, right?

The idea is to BFS process the graph (take start to end… middle(s) as a GRAPH), then easier to come up the quest and map… BFS or DFS always work for this type of questions.

Key is that record the processed, and push cur into queue… don't update the size if the String already is in the map to guarantee the shortest path…

Difference one from word ladder II, not necessary to save level information… just loop, return if reached.


public class Solution {
    public int ladderLength(String start, String end, HashSet<String> dict) {
       if(dict.size() == 0){
           return 0;
       }
       if(start.equals(end)){
           return 1;
       }
       Queue<String>  process = new LinkedList<String>();
       Map<String, Integer> processed = new HashMap<String, Integer>();
       process.offer(start);
       processed.put(start, 1);
       while(!process.isEmpty()){
           String curProcess = process.poll();
           int size = processed.get(curProcess);
           for(int i = 0; i < curProcess.length(); i++){
               StringBuilder processing = new StringBuilder(curProcess);
               for(char c = 'a'; c <= 'z'; c++){
                   processing.setCharAt(i, c);
                   String cur = processing.toString();
                   if(cur.equals(end)){
                       return size + 1;
                   }
                   if(dict.contains(cur) && !processed.containsKey(cur)){
                       process.offer(cur);
                       processed.put(processing.toString(), size + 1);
                   }
               }
           }
       }
       return 0;
    }
}