Solution to https://leetcode.com/problems/word-ladder/

solve.py

class Solution:
    # @param beginWord, a string
    # @param endWord, a string
    # @param wordDict, a set<string>
    # @return an integer
    def is_intermediate(self, a, b):
        return len(filter(lambda x: x, [a[i] != b[i] for i in range(len(a))])) == 1
    
    def dfs(self, themap, start, end, limit):
        if limit <= 0:
            return 0
        if start == end:
            return 1
        else:
            inter = [self.dfs(themap, e, end, limit-1) for e in themap[start]]
            if inter:
                return 1 + min(inter)
            else:
                return 0
    
    def ladderLength(self, beginWord, endWord, wordDict):
        
        themap = {}
        wordDict = set(list(wordDict) + [beginWord, endWord])
        
        for s in wordDict:
            themap[s] = []
        
        for start in wordDict:
            for end in wordDict:
                if self.is_intermediate(start, end):
                    themap[start].append(end)

        return self.dfs(themap, beginWord, endWord, len(beginWord))