# One HashMap, one queue, with comment

• Actually we could consider this problem as the shortest path problem in a graph. So we could use the idea of Dijkstra shortest path algorithm to solve it. Every time we search the next layer until we reach the end point.

``````public class Solution {
private class WTN
{
String cur = new String();
int step;
public WTN(WTN node, String s, int step)
{
this.cur = new String(s);
this.step = step;
}
}
public List<List<String>> findLadders(String beginWord, String ew, Set<String> wordList) {
HashMap<String, WTN> set = new HashMap<>(); // point set which we have alread reached
int min = Integer.MAX_VALUE;
boolean next = false;
WTN head = new WTN(null, beginWord, 0);     // to build graph

while (!queue.isEmpty())
{
WTN curr = queue.removeFirst();
int step = curr.step;
if (step + 1 > min) break;
next = false;
// which position to change
for (int i = 0; !next && i < curr.cur.length(); i++) {
StringBuilder temp = new StringBuilder(curr.cur);
// change into which letter in position i
for (char c = 'a'; c <= 'z'; c ++) {
temp.setCharAt(i, c);
String nw = temp.toString();
if (nw.equals(ew)){
getPath(curr, ret, listT); // backtrack
min = step + 1;
next = true;
break;
}

if (wordList.contains(nw)) {
if (!set.containsKey(nw)){
WTN nn = new WTN(curr, nw, step + 1);
set.put(nw, nn);
}
else if (set.get(nw).step == step + 1)
}
} // end of letter choice
} // end of position choice
} // end of while
return ret;
}

private void getPath(WTN bw, List<List<String>> ret, LinkedList<String> list)
{
if (bw == null){