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

"hot"
"dog"
["hot","dog"]

import sys

class Solution:
    usedSet = set()
    results = {}
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if beginWord == endWord:
            return 1
        if beginWord in Solution.results:
            return Solution.results[beginWord]

        best = sys.maxsize
        for word in wordList:
            if word in Solution.usedSet or not self.islegal(beginWord, word):
                continue
            Solution.usedSet.add(word)
            route = self.ladderLength(word, endWord, wordList)
            Solution.usedSet.remove(word)
            if route > 0 and route < best:
                best = route
        result = best + 1 if best < sys.maxsize else 0
        Solution.results[beginWord] = result
        return result

    def islegal(self, w1, w2):
        return sum([0 if w1[i] == w2[i] else 1 for i in range(len(w1))]) == 1