Leetcode: Word Ladder II

By | 2018 年 7 月 14 日

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[][]}
def find_ladders(begin_word, end_word, word_list)
    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 = [[0]]
    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

发表评论

电子邮件地址不会被公开。 必填项已用*标注