126. Word Ladder II

-
https://leetcode.com/problems/word-ladder-ii/

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
  1. Only one letter can be changed at a time
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
  • Return an empty list if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.
Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
----
Related problems
127-word-ladder
---
Intuition
Shortest path => BFS

We need to return all paths
So save the prefix path on Q with ArrayList

2 Modifications to traditional BFS

  1. We need all shortest paths, so we do not exit on first match, but record that this level found shortest path but continue exploring candidates at the same level. We terminate while loop at !Q.isEmpty() && !found so we do not explore paths longer than shortest
  2. We cannot update global visited right when we add it to the Q, because other neighbors still have to reach the target. So we capture visited for a level, and update global visited at the end of level
Generate neighbors on the fly with a helper function

Convert string to char array
Traverse L to R
Save original char at position i
Loop char a to z
if (char a == original ) continue -- no op
replace char[i] = c
if (new String is not visited)
add it to neighbor

revert char at i to original saved char
---