1.2 Word Ladder

Assumptions:

1. All words have the same length;

2. All words contain only lowercase alphabetic characters;

3. No duplicate in the word list;

4. The beginWord and endWord are not empty and not the same

Input: String beginWord, endWord, List<String> wordList

Output: int length of the transformation

Solution:

1. Use a hashset to store all available step words and a hashset to record visited word

2. Use a queue to store all possible step words for each valid change

3. for each level, try to change characters one by one, until:

3.1 Found a valid step word

Case 1: if the step word is endWord, return the ladder length

Case 2: if not, add the step word to the queue, and add to hashset visited

3.2 Used up all possible combinations and can't find a valid step word, return 0.

TC: O(wordList.length()*word.length()*26)

SC: O(wordList.length()*word.length())

public int wordLadder(String beginWord, String endWord, List<String> wordList) {
  Set<String> wordSet = new HashSet<>(wordList);
  if (wordSet.size() == 0 || !wordSet.contains(endWord)) { return 0; }
  wordSet.remove(beginWord);

  Queue<String> queue = new LinkedList<>();
  queue.offer(beginWord);
  Set<String> visited = new HashSet<>();
  visited.add(beginWord);
  
  int step = 1;
  while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
      String curWord = queue.poll();
      if (changeWord(curWord, endWord, queue, visited, wordSet)) {
        return step + 1;
      }
    }
    step++;
  }
  return 0;
}

private boolean changeWord(String curWord, String endWord, Queue<String> queue, Set<string> visited, Set<String> wordSet) {
  char[] array = curWord.toCharArray();
  for (int i = 0; i < endWord.length(); i++) {
    char preChar = array[i];
    for (char j = 'a'; j <= 'z'; j++) {
      if (j == preChar) { continue; }
      array[i] = j;
      String nextWord = String.valueOf(array);
      if (wordSet.contains(nextWord)) {
        if (nextWord.equals(endWord)) { return true; }
        if (!visited.contains(nextWord)) {
 	queue.add(nextWord);
  	visited.add(nextWord);
        }
      }
    }
    array[i] = preChar;
  }
  return false;
}

Follow-up 1: Print the shortest ladder

Idea: Use predecessor to store the word that we generated from. A Hashmap is needed. After generating a word, dedup by checking in the map.

Follow-up 2: Print all shortest ladders Idea: Either store all predecessors or use DFS on each path from each node.