边工作边刷题：70天一遍leetcode: day 13

Word Ladder I/II

网上著名的难题，一般被黑了都说自己被考了Word Ladder。其实这题I还好，II比较变态，不过知道答案了不难理解。
要点：

• 因为是最短长度，所以bfs找到的可以从字典里去掉。
• bfs从两头做最好，哪个方向集合元素少就作为下一轮的种子

google还考过扩展：减字符找最长路径。意思是一样的。

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: Set[str]
        :rtype: int
        """
        minLen = 2
        if beginWord == endWord: return minLen
        start = [beginWord]
        end = [endWord]
        while start:
            next = []
            for w in start:
                for i in range(len(w)):
                    for c in string.ascii_lowercase:
                        if c!=w[i]:
                            w2 = w[:i]+c+w[i+1:]
                            if w2 in end:
                                return minLen
                            if w2 in wordList:
                                next.append(w2)
                                wordList.remove(w2)
            if len(next)<len(end):
                start = next
            else:
                start = end
                end = next
            minLen+=1
        return 0