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;
    }
}

120. Word Ladder （Self， WA）

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

Thinking:
分为

1. 记录transformation的过程（记录如何变化的）
1. helper function 用来判断是否还剩一步就能变化成功，即与目标单词之差一个letter 
2. dfs
3. 如果在一次dfs中已经变化过那就可以从set去除了
2. 比较得到最短的tranformation
1. 设立rst为Integer.MAX_VALUE;

Leetcode discussion

1. It’s much faster than one-end search indeed as explained in wiki.
2. BFS isn’t equivalent to Queue. Sometimes Set is more accurate representation for nodes of level. (also handy since we need to check if we meet from two ends)
3. It’s safe to share a visited set for both ends since if they meet same string it terminates early. (vis is useful since we cannot remove word from dict due to bidirectional search)
4. It seems like if(set.add()) is a little slower than if(!contains()) then add() but it’s more concise.

 unsolved:
public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        Set<String> reached = new HashSet<String>();
        reached.add(beginWord);
        wordDict.add(endWord);
        int distance = 1;
        while (!reached.contains(endWord)) {
            Set<String> toAdd = new HashSet<String>();
            for (String each : reached) {
                for (int i = 0; i < each.length(); i++) {
                    char[] chars = each.toCharArray();
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        chars[i] = ch;
                        String word = new String(chars);
                        if (wordDict.contains(word)) {
                            toAdd.add(word);
                            wordDict.remove(word);
                        }
                    }
                }
            }
            distance++;
            if (toAdd.size() == 0) return 0;
            reached = toAdd;
        }
        return distance;