[LeetCode] 126. 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.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

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.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Thought process:

1. Build graph: create a Node class which has a previous pointer for backtracking. 
2. BFS: when destination is reached, backtrack and add path to result list.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

public class Solution { private class Node { String word; Node previous; Node(String word, Node previous) { this.word = word; this.previous = previous; } } public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) { Queue<Node> queue = new LinkedList<>(); queue.offer(new Node(beginWord, null)); Set<String> unvisited = new HashSet<>(); unvisited.addAll(wordList); unvisited.remove(beginWord); Set<String> visited = new HashSet<>(); visited.add(beginWord); List<List<String>> ladders = new ArrayList<>(); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { Node node = queue.poll(); if (node.word.equals(endWord)) { List<String> ladder = new ArrayList<>(); while (node != null) { ladder.add(node.word); node = node.previous; } Collections.reverse(ladder); ladders.add(ladder); continue; } char[] chars = node.word.toCharArray(); for (int j = 0; j < chars.length; j++) { char temp = chars[j]; for (char c = 'a'; c <= 'z'; c++) { chars[j] = c; String next = new String(chars); if (unvisited.contains(next)) { visited.add(next); queue.offer(new Node(next, node)); } } chars[j] = temp; } } unvisited.removeAll(visited); } return ladders; } }

Time complexity: 

Say number of words = V and length of each word = l. while loop and the first for loop takes O(V) as a whole. Backtracking takes O(V). Finding neighbors takes O(l). The overall time complexity is O(V(V + l)).