- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址: https://leetcode.com/problems/word-ladder/description/
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
1、 Onlyonelettercanbechangedatatime.;
2、 Eachtransformedwordmustexistinthewordlist.NotethatbeginWordisnotatransformedword.;
Note:
Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
这个题名字是词语梯子,简单理解就是从begin开始,每次只能替换已经转化了的单词的其中一个字符,看最终能不能得到end。有个要求就是,每次变化不是任意的,是必须变成wordList中的其中一个才行。
拿到这个题没有什么思路,看了别人解答之后,才猛然发现这个题是走迷宫问题的变形!也就是说,我们每次变化有26个方向,如果变化之后的位置在wordList中,我们认为这个走法是合规的,最后问能不能走到endWord?
很显然这个问题是BFS的问题,只是把走迷宫问题的4个方向转变成了26个方向,直接BFS会超时,所以我使用了个visited来保存已经遍历了的字符串,代表已经走过了的位置。代码总体思路很简单,就是利用队列保存每个遍历的有效的字符串,然后对队列中的每个字符串再次遍历,保存每次遍历的长度即可。
时间复杂度是O(NL),空间复杂度是O(N).其中N是wordList中的单词个数,L是其实字符串的长度。
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
wordset = set(wordList)
if endWord not in wordset:
return 0
visited = set([beginWord])
chrs = [chr(ord('a') + i) for i in range(26)]
bfs = collections.deque([beginWord])
res = 1
while bfs:
len_bfs = len(bfs)
for _ in range(len_bfs):
origin = bfs.popleft()
for i in range(len(origin)):
originlist = list(origin)
for c in chrs:
originlist[i] = c
transword = "".join(originlist)
if transword not in visited:
if transword == endWord:
return res + 1
elif transword in wordset:
bfs.append(transword)
visited.add(transword)
res += 1
return 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
显然上面的这个做法还是可以变短一点的,想起之前的二叉树的BFS的时候,会在每个节点入队列的时候同时保存了这个节点的深度,这样就少了一层对bfs当前长度的循环,可以使得代码变短。同时,学会了一个技巧,直接把已经遍历过的位置从wordList中删除,这样就相当于我上面的那个visited数组。下面这个代码很经典了,可以记住。
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
wordset = set(wordList)
bfs = collections.deque()
bfs.append((beginWord, 1))
while bfs:
word, length = bfs.popleft()
if word == endWord:
return length
for i in range(len(word)):
for c in "abcdefghijklmnopqrstuvwxyz":
newWord = word[:i] + c + word[i + 1:]
if newWord in wordset and newWord != word:
wordset.remove(newWord)
bfs.append((newWord, length + 1))
return 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
参考资料:
http://www.cnblogs.com/grandyang/p/4539768.html
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我有问题,我需要在哪里用不同的逻辑来实现梯子问题。 在每一步中,玩家必须向单词添加一个字母从上一步中删除一个字母,然后重新排列字母以组成一个新单词。 羊角面包(-C) -> 纵火犯(-S) -> ar
题目地址: https://leetcode.com/problems/word-ladder/description/ 题目描述: Given two words (beginWord and
我遇到了一个问题,当我想用nodejs、express和mysql以“阶梯”形式进行查询并返回一个json时,它对我不起作用,我想要的结构是: select dev_id*,dev_name fr
你们都知道梯子和鸡蛋的问题,您需要在梯子和鸡蛋中找到最高的梯级,使掉落的鸡蛋不会破裂。 问题在 stackoverflow 上针对 100 个梯级和 2 个鸡蛋的情况进行了解释,但是当你有一个无限梯子
我是一名学生,正在开发一款 Chutes and Ladders 游戏。我正在使用方法来确定应该在游戏板上放置多少个滑槽和梯子。我在 main using 参数中为每个参数指定了 10 个,但我一直在
问题: Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transfo
我正在尝试修改我为一个玩家在 Swift 中为一个简单的蛇梯游戏创建的代码。下面是一个成功运行的代码: let finalSquare = 25 var playersLocation: Int =
我在看 tweetylicious source from github研究 Mojolicious 框架: 但是我对下面的代码感到困惑 ladder sub ... .它在 Perl 中是什么意思?
我有一个像这样的 Pandas 数据框: color cost temp 0 blue 12.0 80.4 1 red 8.1 8
这是我应该做的: 你的 friend 想尝试做一个字梯!这是一个单词列表,其中每个单词与其前面的单词有一个字母的差异。这是一个例子: cat cot cog log 编写一个程序来帮助你的 frien
我正在尝试解决所有关于 codility 的类(class),但我未能解决以下问题:Ladder by codility 我在整个互联网上进行了搜索,但没有找到令我满意的答案,因为没有人回答为什么最大
预期是从输入列表 items 派生 3 个列表 itemIsBoth、aItems、bItems。如何将下面的代码转换为功能样式? (我知道这段代码在命令式风格中已经足够清晰了,但我想知道声明式风格是
我是一名优秀的程序员,十分优秀!