## Question

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.

e.g.
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

## Analyze

This is a graph search problem. Each word is a node in graph. Each pair of nodes has only 1 character diff has an edge connecting them. By this representation, the problem transformed into finding paths connecting start_word and end_word with minimum steps.

We can do this from the start_word, in each step, expanding the paths by 1 step following the edges. Taking the example above: In the graph above, number besides the arrow indicate the step#. So in step4, we got 2 paths from start_word to end_word.

## Performance

This question is easily got into time out error, especially I chosen ruby in the beginning. > 95% time is spent to optimize the performance.

The optimizations I tried:

• use bi-directional search (from start_word and end_word simultaneously) instead of 1 way;
• balanced bi-directional search, only expanding the smaller side;
• build map when needed;
• use `while` instead of `each_with_index`;
• use `each` loop instead of the ruby way of `select`, `map`, `reject`, etc.

Actually, after drawing the graph, I found another optimization to this problem. We can adapt the A* algorithm with constant 1 edge weight. Which should be easily avoid the TLE error. By this, we can avoid expanding the paths contains the vertical #3/#4 edges above.

## Solutions

### Ruby

Rewrote several statements into non-ruby way for speed. e.g.

`while` is faster than `each_with_index`;

`each` loop is faster than `select`, `map` combinations.

```# @param {String} begin_word
# @param {String} end_word
# @param {String[]} word_list
# @return {String[][]}
timestamp = Time.now
checkpoint = timestamp

word_list = [begin_word] + word_list

idx_end = word_list.index(end_word)
return [] if idx_end.nil?

possible_paths_d1 = []
possible_paths_d2 = [[idx_end]]
solution_paths = nil

map = {}

p "Map built: #{Time.now - checkpoint}, total: #{Time.now - timestamp}"
checkpoint = Time.now

word_list.length.times do
possible_paths_d1, solution_paths = extend_possible_paths(possible_paths_d1, possible_paths_d2, map, word_list)
p "Run: #{'%.3f' % (Time.now - checkpoint)}, total: #{'%.3f' % (Time.now - timestamp)}, map: #{map.size}"

if solution_paths.size > 0
return solution_paths.map{|path| path.map{|idx| word_list[idx]}}
end
if possible_paths_d1.size > possible_paths_d2.size
possible_paths_d1, possible_paths_d2 = possible_paths_d2, possible_paths_d1
end

checkpoint = Time.now
end

return []
end

def extend_possible_paths(possible_paths, target_paths, map, word_list)
target_idxs = {}
target_paths.each do |path|
target_idxs[path.last] = true
end

new_paths = []
solution_paths = []

possible_paths.each do |path|
checking_word_idx = path.last
possible_nexts = map[checking_word_idx] || build_map(word_list, map, checking_word_idx)

possible_nexts.each do |next_idx|
next if path.include?(next_idx)
new_path = path.clone << next_idx
new_paths << new_path
if target_idxs[next_idx]
solution_paths << new_path
end
end
end

if solution_paths.size > 0
full_solution_paths = []
solution_paths.each do |path|
full_solution_paths += target_paths.
select{|target_path| target_path.last == path.last}.
map{|target_path| path.clone[0..-2] + target_path.clone.reverse}
end
full_solution_paths = full_solution_paths.map{|path| path.first == 0 ? path : path.reverse}
solution_paths = full_solution_paths
end

return [new_paths, solution_paths]
end

def is_connected(w1, w2)
diff = 0
idx = 0
while idx < w1.size
diff += 1 unless w1[idx] == w2[idx]
return false if diff > 1
idx += 1
end
return diff == 1
end

def build_map(word_list, map, idx)
return unless map[idx].nil?
map[idx] = []
word = word_list[idx]
idx_target = 0
while idx_target < word_list.size
target = word_list[idx_target]
if idx_target != idx && is_connected(word, target)
map[idx] << idx_target
end
idx_target += 1
end
return map[idx]
end
```