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

ladderLength.java

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

Only one letter can be changed at a time
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.
*/

import java.util.*;
public class Solution {
    ArrayList<String> seen = new ArrayList<String>();
    public int ladderLength(String start, String end, HashSet<String> dict) {
        // Start typing your Java solution below
        // DO NOT write main() function
        // depth first search to find the solution
        int cur = 1;
        int min = Integer.MAX_VALUE;
        seen.clear();
        ArrayList<String> list = new ArrayList<String>();
        copy(dict, list);
        int min_length = dfs(start, end, list, cur, min);
        if(min_length == Integer.MAX_VALUE) return 0; 
        else return min_length;
    }
    
    public void copy(HashSet<String> dict, ArrayList<String> list) {
        Iterator<String> itr = dict.iterator();
        while(itr.hasNext()) {
            String tmp = itr.next();
            list.add(tmp);
            itr.remove();
        }
        return;
    }
    
    public ArrayList<String> next(String needle, ArrayList<String> ary) {
        ArrayList<String> list = new ArrayList<String>();
        int mismatch = 0;
        int maxmix = 1;
        int size = needle.length();
        int index = ary.size() - 1;
        
        while(index >= 0) {
            String tmp = ary.get(index);
            if(seen.indexOf(tmp) >= 0) {
                index--;
                continue;
            }
            for(int i = 0; i < size; i++) {
                if(needle.charAt(i) != tmp.charAt(i)) {
                    mismatch++;
                }
            }
            if(mismatch == 1) {
                list.add(tmp);
            }
            mismatch = 0;
            index--;
        }
        return list;
    }
    
    public int dfs(String start, String end, ArrayList<String> list, int cur, int min) {
        seen.add(start);
        ArrayList<String> nexts = next(start, list);
        for(String next: nexts) {
            if(next.equals(end)) {
                if((cur+1) < min) {
                    min = cur+1;
                }
                return min;
            }
            min = dfs(next, end, list, cur + 1, min);
            seen.remove(next);
        }
        return min;
    }
}