Word Ladder II

In [1]:

    

import sys; sys.path.append('../..')
from puzzles import leet_puzzle
leet_puzzle('word-ladder-ii')


    

    





Source : https://leetcode.com/problems/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:


Only one letter can be changed at a time
Each intermediate word must exist in the word list


For example,


Given:

beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log"]



Return

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


Note:


All words have the same length.
All words contain only lowercase alphabetic characters.







Array
Backtracking
Breadth-first Search
String

In [8]:

    

import itertools


def simple_distance(s1, s2):
    return sum(c1 != c2 for c1, c2 in itertools.izip(s1, s2))


def get_transformations(begin_word, end_word, valid_words):
    
    results = set()
    for permutation in itertools.permutations(valid_words + [end_word]):
        
        result = []
        word = begin_word
        
        for valid_word in permutation:
            if simple_distance(word, valid_word) == 1:
                result += [valid_word]
                word = valid_word
                
        if len(result) and result[-1] == end_word:
            results.add(tuple([begin_word] + result))
            
    return results


def word_ladder_2(begin_word, end_word, valid_words):
    
    assert len(begin_word) == len(end_word)
    
    transformations = get_transformations(begin_word, end_word, valid_words)
    
    shortest_len = len(min(transformations, key=len))
    shortest = [x for x in transformations if len(x) == shortest_len]
    
    return shortest


actual = word_ladder_2("hit", "cog", ["hot","dot","dog","lot","log","cat"])
expected = [('hit', 'hot', 'lot', 'log', 'cog'), ('hit', 'hot', 'dot', 'dog', 'cog')]
for result in sorted(actual):
    print result
assert sorted(expected) == sorted(actual)


    

    




('hit', 'hot', 'dot', 'dog', 'cog')
('hit', 'hot', 'lot', 'log', 'cog')

In [21]:

    

%%timeit
word_ladder_2("hit", "cog", ["hot","dot","dog","lot","log","cat"])


    

    




10 loops, best of 3: 68 ms per loop

In [12]:

    

import collections, itertools, sys


def simple_distance(s1, s2):
    return sum(c1 != c2 for c1, c2 in itertools.izip(s1, s2))


def build_graph(words):
    
    graph = collections.defaultdict(list)
    
    for word1, word2 in itertools.permutations(words, 2):
        if simple_distance(word1, word2) == 1:
            graph[word1].append(word2)
            
    return graph


def find_shortest_paths(graph, start, end, path=None):
    
    path = path or []
    path = path + [start]
    
    if start == end:
        return [path]
    
    if not graph.has_key(start):
        return None
    
    shortest = []
    
    for node in graph[start]:
        if node not in path:
            newpath = find_shortest_paths(graph, node, end, path)
            if newpath:
                if not shortest or len(newpath[0]) < len(shortest[0]):
                    shortest = newpath
                elif len(newpath[0]) == len(shortest[0]):
                    shortest += newpath
              
    return shortest

    
def word_ladder_2(begin, end, valid_words):
    graph = build_graph(words + [begin, end])
    return [
        tuple(x)
        for x in find_shortest_paths(graph, begin, end)
    ]
    
    
words = ["hot", "dot", "dog", "lot", "log", "cat"]
begin, end = "hit", "cog"
actual = word_ladder_2(begin, end, words)
for result in sorted(actual):
    print result
assert sorted(expected) == sorted(actual)


    

    




('hit', 'hot', 'dot', 'dog', 'cog')
('hit', 'hot', 'lot', 'log', 'cog')

In [13]:

    

%%timeit
words = ["hot","dot","dog","lot","log","cat"]
begin, end = "hit", "cog"
word_ladder_2(begin, end, words)


    

    




10000 loops, best of 3: 133 µs per loop