120. Word Ladder

思路：

1. 确认空集，开始词等于结束词的特殊情况
2. 将start string放入queue
3.  length = 1
4. queue进行操作获取当前string的所有transformation
5. 判断dict中是否存在transformation
6. 判断hash中是否已经出现过这个transformation
7. 4 && 5 都没有发生，判断是否为end。 是， 返回length
8. 过即为可能的next level string 加入queue 同时加入hash
1. 任何后出现的同一个transformation string 都是相同length 或者length + 1...
9. 循环直到queue空返回0

public class Solution {
    /*
     * @param start: a string
     * @param end: a string
     * @param dict: a set of string
     * @return: An integer
     */
    public int ladderLength(String start, String end, Set<String> dict) {
      if (dict == null) {
          return 0;
      }
     
      if (start.equals(end)) {
          return 1;
      }
     
      dict.add(start);
      dict.add(end);
     
      // HashSet检查这个word是否已经作为一个transformation出现过
      HashSet<String> hash = new HashSet<String>();
     
      Queue<String> queue = new LinkedList<String>();
      queue.offer(start);
      hash.add(start);
     
      int length = 1;
      //
      while(!queue.isEmpty()) {
          length++;
          int size = queue.size();
          for (int i = 0; i < size; i++) {
              String word = queue.poll();
              // 获得所有现在word的transformation结果
              // CE: typo getnextWords
              for (String nextWord: getNextWords(word, dict)) {
                  // 判断这个transformation出现过没有
                  if (hash.contains(nextWord)) {
                      continue;
                  }
                  if (nextWord.equals(end)) {
                      return length;
                  }
                 
                  hash.add(nextWord);
                  queue.offer(nextWord);
              }
          }
      }
      return 0;
    }
   
    // replace character of a string at given index to a given character
    // return a new string
    private String replace(String s, int index, char c) {
        // CE: typo charp
        char[] chars = s.toCharArray();
        // CE: typo
        chars[index] = c;
        return new String(chars);
    }
   
    // get connections with given word.
    // for example, given word = 'hot', dict = {'hot', 'hit', 'hog'}
    // it will return ['hit', 'hog']
    private ArrayList<String> getNextWords(String word, Set<String> dict) {
        ArrayList<String> nextWords = new ArrayList<String>();
        for (char c = 'a'; c <= 'z'; c++) {
            for (int i = 0; i < word.length(); i++) {
                if (c == word.charAt(i)) {
                    continue;
                }

                String nextWord = replace(word, i ,c);
                if (dict.contains(nextWord)) {
                    nextWords.add(nextWord);
                }
            }
        }
        return nextWords;
    }
}