[leetcode/lintcode 题解] 阿里算法面试题:单词接龙 II

简介: [leetcode/lintcode 题解] 阿里算法面试题:单词接龙 II

描述
给出两个单词(start和end)和一个字典,找出所有从start到end的最短转换序列。
变换规则如下:

  1. 每次只能改变一个字母。
  2. 变换过程中的中间单词必须在字典中出现。

所有单词具有相同的长度。
所有单词都只包含小写字母。
题目确保存在合法的路径。

在线评测地址:领扣题库官网

样例1
输入:start = "a",end = "c",dict =["a","b","c"]
输出:[["a","c"]]
解释:
"a"->"c"
样例2
输入:start ="hit",end = "cog",dict =["hot","dot","dog","lot","log"]
输出:[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释:
1."hit"->"hot"->"dot"->"dog"->"cog"
2."hit"->"hot"->"lot"->"log"->"cog"

从 end 到 start 做一次 BFS,并且把距离 end 的距离都保存在 distance 中。 然后在从 start 到 end 做一次 DFS,每走一步必须确保离 end 的 distance 越来越近。
与另外一个代码中提前建立 index 不同,这里是在寻找下一个变换单词的时候,再去获得对应的单词列表。一个单词最多有 L 个字符,每个字符有 25 种不同的变化(26个字母除掉这个位置上的字母),然后 check 一下在不在 dict 里就知道是不是 next word 了。
from collections import deque

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):
        dict.add(start)
        dict.add(end)
        distance = {}

        self.bfs(end, distance, dict)

        results = []
        self.dfs(start, end, distance, dict, [start], results)

        return results

    def bfs(self, start, distance, dict):
        distance[start] = 0
        queue = deque([start])
        while queue:
            word = queue.popleft()
            for next_word in self.get_next_words(word, dict):
                if next_word not in distance:
                    distance[next_word] = distance[word] + 1
                    queue.append(next_word)

    def get_next_words(self, word, dict):
        words = []
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i + 1:]
                if next_word != word and next_word in dict:
                    words.append(next_word)
        return words

    def dfs(self, curt, target, distance, dict, path, results):
        if curt == target:
            results.append(list(path))
            return

        for word in self.get_next_words(curt, dict):
            if distance[word] != distance[curt] - 1:
                continue
            path.append(word)
            self.dfs(word, target, distance, dict, path, results)
            path.pop()

更多题解参考:九章官网solution

相关文章
|
存储 人工智能 算法
从零掌握贪心算法Java版:LeetCode 10题实战解析(上)
在算法世界里,有一种思想如同生活中的"见好就收"——每次做出当前看来最优的选择,寄希望于通过局部最优达成全局最优。这种思想就是贪心算法,它以其简洁高效的特点,成为解决最优问题的利器。今天我们就来系统学习贪心算法的核心思想,并通过10道LeetCode经典题目实战演练,带你掌握这种"步步为营"的解题思维。
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
316 0
|
算法
测试工程师的技能升级:LeetCode算法挑战与职业成长
这篇文章通过作者亲身体验LeetCode算法题的过程,探讨了测试工程师学习算法的重要性,并强调了算法技能对于测试职业成长的必要性。
568 1
测试工程师的技能升级:LeetCode算法挑战与职业成长
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
564 4
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
329 6
|
存储 算法 Java
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
391 2
LeetCode第58题最后一个单词的长度
LeetCode第58题"最后一个单词的长度"的解题方法,通过从字符串末尾向前遍历并计数非空格字符,直接得出最后一个单词的长度。
LeetCode第58题最后一个单词的长度
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
350 1
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
378 1
Leetcode(最后一个单词长度)
这篇文章介绍了两种解决LeetCode第58题的方法,即计算给定字符串中最后一个单词的长度,方法包括翻转字符串和逆向遍历统计。
212 0

热门文章

最新文章