Leetcode–Word Ladder

The Problem:

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Notes:

  1. At first I was considering using recursion, which results in a “DFS” structure, and need to keep track of min steps, because it may already traverse down too far in one recursion then reach the end, yet in other branches may only need much fewer steps. This is an indication that we should use “BFS” instead.
  2. When using BFS, we need 3 things:
    1. a queue to hold “next start”
    2. a set to record the strings already visited, to avoid trapped in a loop
    3. since we need to return the steps, it needs to pair with the string in queue. So I used a wrapper class.

Java Solution I-DFS

public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        if(start.equals(end)) return 1;
        char[] arr = start.toCharArray();
        int min = Integer.MAX_VALUE;
        for(int i = 0; i <start.length(); i++){
            char temp = arr[i];
            for(char ch = 'a'; ch <='z'; ch++){
                if(ch != temp){
                    arr[i] = ch;
                    String nxt = new String(arr);
                    if(end.equals(nxt))
                        return 2;
                    else if(dict.contains(nxt)){
                        dict.remove(nxt);
                        min = Math.min(min, 1+ ladderLength(nxt, end, dict));
                        dict.add(nxt);
                    }
                }
            }
            arr[i] = temp;
        }
        return min==Integer.MAX_VALUE ? 0:min;
    }
}

Java Solution II-BFS

public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        if(start.equals(end)) return 1;
        Queue<WrapStr> q = new LinkedList<WrapStr>();
        Set<String> visited = new HashSet<String>();
        q.add(new WrapStr(start, 1));
        visited.add(start);
        while(!q.isEmpty()){
            WrapStr wp = q.poll();
            char[] arr = wp.str.toCharArray();
            for(int i = 0; i <arr.length; i++){
                char temp = arr[i];
                for(char ch = 'a'; ch <='z'; ch++){
                    if(ch != temp){
                        arr[i] = ch;
                        String nxt = new String(arr);
                        if(end.equals(nxt))
                            return wp.steps+1;
                        else if(!visited.contains(nxt) && dict.contains(nxt)){
                            q.add(new WrapStr(nxt, wp.steps+1));
                            visited.add(nxt);
                        }
                    }
                }
                arr[i] = temp;
            }
        }
        return 0;        
    }
}
class WrapStr{
    public String str;
    public int steps;
    public WrapStr(String s, int l){
        str = s;
        steps = l;
    }
}