127._word_ladder.md

###127. Word Ladder

题目:

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

难度:

Medium

tag可以算BFS，其实就是求shortest path的变体

按照BFS的微码改了一下，尝试AC，超时

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: Set[str]
        :rtype: int
        """
        queue = [(beginWord, [beginWord])]
        visited = set()

        while queue:
            (vertex, path) = queue.pop(0)
            if vertex not in visited:
                if self.oneDiff(vertex, endWord):
                    return len(path) + 1
                visited.add(vertex)
                for word in wordList:
                    if self.oneDiff(vertex, word):
                        queue.append((word, path + [word]))
        return 0

    def oneDiff(self,s1, s2):
        countDiffs = 0
        for a, b in zip(s1,s2):
            if a != b:
                countDiffs += 1
        return countDiffs == 1

着手优化

实在发现优化基本无所提升，然后看别人的解法，思路一致，但是用了collection里面的结构deque和增加set帮助解题。

collection有待研究

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: Set[str]
        :rtype: int
        """
        from collections import deque, defaultdict

        queue = deque([(beginWord, [beginWord])])        
        visited = set()
        wordSet = set(wordList)
        wordSet.add(endWord)

        while queue:
            (vertex, path) = queue.popleft()
            if vertex not in visited:
                if vertex == endWord:
                    return len(path)
                visited.add(vertex)
                for i in range(len(beginWord)):
                    part1 = vertex[:i]; part2 = vertex[i+1:]
                    for j in 'abcdefghijklmnopqrstuvwxyz':
                        if vertex[i] != j:
                            nextWord = part1 + j + part2
                            if nextWord in wordSet:
                                queue.append((nextWord, path + [nextWord]))
                                wordSet.remove(nextWord)
        return 0