263ms Easy to Understand Java Solution Using Simple BFS

• Inspired by Share two similar Java solution that Accptted by OJ.
In order to get the shortest transformations, we can build a graph and then bfs the graph until we get to the level where the `endWord` first appears. All the paths from the `beginWord` to this level are shortest.

The solution is quite simple, we build a graph by bfs to the level where the `endWord` appears. After we scan all the nodes at this level, we could build all the paths with the graph we built.

``````

public class Solution {
Set<String> getOneEditWord(String word, Set<String> dict) {
Set<String> result = new HashSet();
for (int i = 0; i < word.length(); i++) {
for (char j = 'a'; j <= 'z'; j++) {
if (j == word.charAt(i)) continue; // itself
StringBuilder w = new StringBuilder(word);
w.setCharAt(i, j);
String nn = w.toString();
}
}
return result;
}

public void backTrace(Map<String, Set<String>> graph, List<List<String>> result, String start, String end, Deque<String> curPath) {
if (end.equals(start)) {
return;
}

if (null == graph.get(start)) {
return;
}

for (String child : graph.get(start)) {
backtrace(graph, result, child, end, curPath);
curPath.removeLast();
}
}

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Map<String, Set<String>> graph = new HashMap();
Queue<String> toVisit = new ArrayDeque<>();
Map<String, Integer> ladder = new HashMap();

Set<String> dict = new HashSet<>();

int step = 0;
int minStep = Integer.MAX_VALUE;

while (!toVisit.isEmpty()) {
String word = toVisit.poll();
step = ladder.get(word) + 1;
if (step > minStep) break; // the shorttest has been processed
for (String child : getOneEditWord(word, dict)) {
//System.out.println(child);
int cStep = ladder.getOrDefault(child, Integer.MAX_VALUE);
if (cStep < step) continue;
if (cStep > step) {
}
if (graph.containsKey(word)) {
} else {
Set<String> set = new HashSet<>();
graph.put(word, set);
}
if (child.equals(endWord)) {
if (minStep > step) {
minStep = step;
}
}
}
}
//System.out.println(graph);
List<List<String>> result = new LinkedList<>();
Deque<String> bPath = new ArrayDeque<>();
backTrace(graph, result, beginWord, endWord, bPath);
return result;
}

public static void main(String[] args) {
Solution s = new Solution();
String[] dict = new String[]{"hot", "dot", "dog", "lot", "log"};
}
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.