127. 单词接龙 [medium]

127. 单词接龙 [medium]

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

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

• 每次转换只能改变一个字母。
• 转换过程中的中间单词必须是字典中的单词。

说明:

• 如果不存在这样的转换序列，返回 0。
• 所有单词具有相同的长度。
• 所有单词只由小写字母组成。
• 字典中不存在重复的单词。
• 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。

示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: 0

解释: endWord "cog" 不在字典中，所以无法进行转换。

通过次数45,892 | 提交次数108,078

Third Try

2020-06-26

双向BFS版本，算是了解了新的领域。关于图的应用，重点是记录曾经走过的部分，方能防止无限循环。在双向BFS中，记录的还包括某个点的步数/level，这样两边就能很方便汇合起来。

在看过题解之后才写出来的版本，还是有一些tricks在里面的，比如两个队列，每次都先后只走一步，并且记录下一圈的节点在已经遍历走过的部分，这样才能迎来相会，而不是变成了回首（导致多一步，具体看代码注释里的bug提示）。

这里的双向BFS没有简化成函数调用，可以进行修改，但第一遍还是需要手写展开，然后再进行汇合比较方便。

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int

        可怕，超时了，在某个案例上花了2s的时间。。
        初始构建方法修改为泛化字符串字典的模式，竟然只要0.404s即可解决
        没想到初始构建条件的写法差别那么大，亏我在写第一个构建方法的时候还考虑了复杂度的问题，可能是在intersection_update部分耗费时间了
        改成双向BFS，时间又快了
        
        """
        if beginWord == endWord:  # 其实我觉得应该是0才对
            return 1
        if endWord not in wordList:
            return 0
        if beginWord not in wordList:
            wordList.append(beginWord)

        # construct mix_word mapping
        wlen = len(beginWord)
        word_mix = dict()
        graph = {w: set() for w in wordList}
        for word in wordList:
            for i in range(wlen):
                wmix = word[:i] + "*" + word[i+1:wlen] 
                col = word_mix.get(wmix, set())
                col.add(word)
                word_mix[wmix] = col

        # construct graph，经典的图表示法还好没有忘记
        for word in wordList:
            for i in range(wlen):
                graph[word].update(word_mix[word[:i] + "*" + word[i+1:]])
            graph[word].remove(word)  # 并不影响

        # 考虑双向BFS的写法
        start_q = [(1, beginWord)]
        end_q = [(1, endWord)]
        start_visited = dict([(beginWord, 1)]) # 修改为dict是关键，可以保存走过的路程信息
        end_visited = dict([(endWord, 1)])
        # 双向靠近，可以简化为两个函数调用
        while len(start_q) and len(end_q):
            level, node = start_q.pop(0)  # pop(0)而非pop()
            # start_visited[node] = level  # 应该关注的是graph[node]，该轮再添加则晚了
            for n in graph[node]:
                if n in end_visited:
                    return level + end_visited[n]  
                if n in start_visited:
                    continue
                start_visited[n] = level + 1  # 若不在这里添加则有bug，步数多1位，变成了回望而不是首次接触
                start_q.append((level + 1, n))
            
            level, node = end_q.pop(0)  # pop(0)而非pop()
            # end_visited[node] = level
            for n in graph[node]:
                if n in start_visited:
                    return level + start_visited[n]  
                if n in end_visited:
                    continue
                end_visited[n] = level + 1
                end_q.append((level + 1, n))
        return 0

• 执行用时：136 ms, 在所有 Python 提交中击败了55.06%的用户
• 内存消耗：21 MB, 在所有 Python 提交中击败了100.00%的用户

Second Try

2020-06-26

重点一是把问题转化为图的形式，二是BFS在图里的用法与问题的结合，三是初始构建图的模糊字符方法。前两个都可以搞定，第三个写出了个超时版本。

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int

        可怕，超时了，在某个案例上花了2s的时间。。
        初始构建方法修改为泛化字符串字典的模式，竟然只要0.404s即可解决
        没想到初始构建条件的写法差别那么大，亏我在写第一个构建方法的时候还考虑了复杂度的问题，可能是在intersection_update部分耗费时间了
        
        """
        if beginWord == endWord:  # 其实我觉得应该是0才对
            return 1
        if endWord not in wordList:
            return 0
        if beginWord not in wordList:
            wordList.append(beginWord)

        # construct mix_word mapping
        wlen = len(beginWord)
        word_mix = dict()
        graph = {w: set() for w in wordList}
        for word in wordList:
            for i in range(wlen):
                wmix = word[:i] + "*" + word[i+1:wlen]  # 可能会出现abc被转化为abc*的情况，但不影响结局
                col = word_mix.get(wmix, set())
                col.add(word)
                word_mix[wmix] = col

        # construct graph
        for word in wordList:
            for i in range(wlen):
                graph[word].update(word_mix[word[:i] + "*" + word[i+1:]])

        # bfs part for graph
        # 按照总共经历的word数量统计，而不是中间经过多少次切换，这两者之间会有1的差别
        queue = [(1, beginWord)]  
        collected = set()
        # print(graph)
        while len(queue):
            level, node = queue.pop(0)
            print(level, node)
            if endWord in graph[node]:
                # print("HOLA", endWord, node)
                return level + 1
            for n in graph[node]:
                if n in collected:  # cut the circulation
                    continue
                queue.append((level + 1, n))
            collected.add(node)
        return 0

• 执行用时：2272 ms, 在所有 Python 提交中击败了10.12%的用户
• 内存消耗：23.7 MB, 在所有 Python 提交中击败了100.00%的用户

First Try

构建部分仍然是超时部分的版本，但是把BFS改成双向BFS，勉强在1.9s内完成了最长的案例测试，同时也贴线通过上传考核。

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int

        可怕，超时了，在某个案例上花了2s的时间。。
        """
        if beginWord == endWord:  # 其实我觉得应该是0才对
            return 1
        if endWord not in wordList:
            return 0
        if beginWord not in wordList:
            wordList.append(beginWord)

        # construct char idex mapping
        wlen = len(beginWord)
        moc = [dict() for c in beginWord]
        for word in wordList:
            for i in range(wlen):
                if moc[i].get(word[i]):
                    moc[i][word[i]].add(word)
                else:
                    moc[i][word[i]] = set([word])  # set("abc") = set("a", "b", "c")

        # construct graph
        graph = {w: set() for w in wordList}
        for word in wordList:
            for i in range(wlen):
                full = set(wordList)
                for j in range(wlen):
                    if j != i:
                        full.intersection_update(moc[j][word[j]])
                full.remove(word)
                graph[word].update(full)
        
        # # bfs part for graph
        # queue = [(1, beginWord)]  # 按照word数量统计，而不是中间经过多少次切换，这两者之间会有1的差别
        # collected = set()
        # # print(graph)
        # while len(queue):
        #     level, node = queue.pop(0)
        #     print(level, node)
        #     if endWord in graph[node]:
        #         # print("HOLA", endWord, node)
        #         return level + 1
        #     for n in graph[node]:
        #         if n in collected:  # cut the circulation
        #             continue
        #         queue.append((level + 1, n))
        #     collected.add(node)
        # return 0
        
        # 考虑双向BFS的写法
        start_q = [(1, beginWord)]
        end_q = [(1, endWord)]
        start_visited = dict([(beginWord, 1)]) # 修改为dict是关键，可以保存走过的路程信息
        end_visited = dict([(endWord, 1)])
        # 双向靠近，可以简化为两个函数调用
        while len(start_q) and len(end_q):
            level, node = start_q.pop(0)  # pop(0)而非pop()
            # start_visited[node] = level  # 应该关注的是graph[node]，该轮再添加则晚了
            for n in graph[node]:
                if n in end_visited:
                    return level + end_visited[n]  
                if n in start_visited:
                    continue
                start_visited[n] = level + 1  # 若不在这里添加则有bug，步数多1位，变成了回望而不是首次接触
                start_q.append((level + 1, n))
            
            level, node = end_q.pop(0)  # pop(0)而非pop()
            # end_visited[node] = level
            for n in graph[node]:
                if n in start_visited:
                    return level + start_visited[n]  
                if n in end_visited:
                    continue
                end_visited[n] = level + 1
                end_q.append((level + 1, n))
        return 0

• 执行用时：9048 ms, 在所有 Python 提交中击败了5.14%的用户
• 内存消耗：16.4 MB, 在所有 Python 提交中击败了100.00%的用户

• time exceeded version

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int

        可怕，超时了，在某个案例上花了2s的时间。。
        """
        if beginWord == endWord:  # 其实我觉得应该是0才对
            return 1
        if endWord not in wordList:
            return 0
        if beginWord not in wordList:
            wordList.append(beginWord)

        # construct char idex mapping
        wlen = len(beginWord)
        moc = [dict() for c in beginWord]
        for word in wordList:
            for i in range(wlen):
                if moc[i].get(word[i]):
                    moc[i][word[i]].add(word)
                else:
                    moc[i][word[i]] = set([word])  # set("abc") = set("a", "b", "c")

        # construct graph
        graph = {w: set() for w in wordList}
        for word in wordList:
            for i in range(wlen):
                full = set(wordList)
                for j in range(wlen):
                    if j != i:
                        full.intersection_update(moc[j][word[j]])
                full.remove(word)
                graph[word].update(full)
        
        # bfs part for graph
        queue = [(1, beginWord)]  # 按照word数量统计，而不是中间经过多少次切换，这两者之间会有1的差别
        collected = set()
        # print(graph)
        while len(queue):
            level, node = queue.pop(0)
            print(level, node)
            if endWord in graph[node]:
                # print("HOLA", endWord, node)
                return level + 1
            for n in graph[node]:
                if n in collected:  # cut the circulation
                    continue
                queue.append((level + 1, n))
            collected.add(node)
        return 0