一起刷leetcode(126): Word Ladder II


原题地址:https://oj.leetcode.com/problems/word-ladder-ii/

题目:
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.
已邀请:

sumnous - 数据挖掘女博士

赞同来自: 一叶知秋 wsk


Python思路:贴一个双向夹逼的方法,得到next_words字典后,再用BFS广搜找到最短路径,参考http://www.tuicool.com/articles/QRrEJz
Python代码(已AC)522ms:
class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return a list of lists of string
    def findLadders(self, start, end, dict):
        # Special cases
        if start == end:
            return [start]
    
        # The length of words
        WORD_LENGTH = len(start)
    
        # New words in one step
        new_words = set()
    
        # Initialize the set of visited words
        start_front = set()
        start_front.add(start)
        start_visited = set()
        start_visited.add(start)
    
        end_front = set()
        end_front.add(end)
        end_visited = set()
        end_visited.add(end)
    
        # Add end to the dictionary
        dict.add(end)
    
        # Traverse map
        next_words = {}
    
        meet = False
        # Extend the two fronts and check if they can meet
        while not meet:
            # Extend the start front
            new_words.clear()
            for w in start_front:
                next_words[w] = []
                for i in xrange(WORD_LENGTH):
                    for candidate in [w[:i]+chr(97+c)+w[i+1:] for c in xrange(26)]:
                        if candidate in dict and candidate not in start_visited:
                            next_words[w].append(candidate)
                            new_words.add(candidate)
            if new_words:
            # Update visited words
                start_visited.update(new_words)
                start_front = new_words.copy()
            else:
                return []
    
            # Check if two fronts meet
            if start_front & end_front:
                break
    
            # Extend the end front
            new_words.clear()
            for w in end_front:
                for i in xrange(WORD_LENGTH):
                    for candidate in [w[:i]+chr(97+c)+w[i+1:] for c in xrange(26)]:
                        if candidate in dict and candidate not in end_visited:
                            next_words.setdefault(candidate, []).append(w)
                            new_words.add(candidate)
            if new_words:
                end_visited.update(new_words)
                end_front = new_words.copy()
            else:
                return []
            # Check if two fronts meet
            if start_front & end_front:
                break
            
        # BFS from start to end
        res = []
        path = [[start]]
        while res == []:
            new_path = []
            for p in path:
                try:
                    for w in next_words[p[-1]]:
                        new_path.append(p+[w])
                        if w == end:
                            res.append(p+[w])
                except:
                    pass
            path = new_path
        # Return all paths in res
        return res

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~