Leetcoder - Word Ladder

 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.

public class Solution {
    public int ladderLength(String start, String end, HashSet<String> dict) {
        // Start typing your Java solution below
        // DO NOT write main() function
// breadth first, graph search, find the shortest path
dict.remove(start);
dict.add(end);

ArrayList<String> fronties = new ArrayList<String>();
fronties.add(start);

boolean find = false;
int level = 1;
loop: while (true) {
level++;
HashSet<String> newFronties = new HashSet<String>();
for (String str : fronties) {
ArrayList<String> nexts = new ArrayList<String>();
for (int i = 0; i < str.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
if (str.charAt(i) != c) {
StringBuilder sb = new StringBuilder();
sb.append(str.subSequence(0, i)).append(c)
.append(str.substring(i + 1));
if (dict.contains(sb.toString())) {
nexts.add(sb.toString());
}
}
}
}
for (String next : nexts) {
if (next.equals(end)) {
break loop;
} else {
newFronties.add(next);
}
}
}
if (fronties.size() == 0) {
   level = 0;
break;
}
dict.removeAll(newFronties);
fronties.clear();
fronties.addAll(newFronties);
}
return level;
}
}


public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        ArrayList<String> frontie = new ArrayList<String>();
        frontie.add(start);
        int step = 1;
        dict.add(end);
        while(frontie.size()!=0 && dict.size()!=0) {
            ArrayList<String> newFrontie = new ArrayList<String>();
            for(String str : frontie) {
                for(int i=0;i<str.length();i++) {
                    int c = str.charAt(i);
                    for(int j='a';j<'z';j++) {
                        if(j==c) continue;
                        String newStr = str.substring(0,i) + ((char) j) + str.substring(i+1);
                        if(dict.contains(newStr)) {
                            if(newStr.equals(end)) return step+1;
                            dict.remove(newStr);
                            newFrontie.add(newStr);
                        }
                    }
                }
            }
            frontie = newFrontie;
            step++;
        }
        return 0;
    }
}

===============

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        Queue<String> queue = new LinkedList<String>();
        queue.add(beginWord);
        int step = 2;
        while (queue.size() != 0 && wordDict.size() != 0) {
            int count = queue.size();
            while (count-- > 0) {
                String str = queue.poll();
                char cs[] = str.toCharArray();
                for (int i = 0; i < str.length(); i++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == str.charAt(i)) {
                            continue;
                        }
                        cs[i] = c;
                        String next = new String(cs);
                        if (next.equals(endWord)) {
                            return step;      
                        }
                        if (wordDict.contains(next)) {
                            wordDict.remove(next);
                            queue.add(next);
                        }
                    }
                    cs[i] = str.charAt(i);
                }
            }
            step++;
        }
        return 0;
    }
}