Leet Code OJ 127. Word Ladder [Difficulty: Medium]-python

本文主要是介绍Leet Code OJ 127. Word Ladder [Difficulty: Medium]-python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

127. Word Ladder

Medium

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. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]Output: 5Explanation: 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: 0Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

题意：

给定一个起始字符串和一个目标字符串，现在将起始字符串按照特定的变换规则转换为目标字符串，求最少要进行多少次转换。转换规则为每次只能改变字符串中的一个字符，且每次转换后的字符串都要在给定的字符串集合中。

思路：

因为每次变换后的字符串都要在给定的字符串组中，所以每次变化的情况都是有限的。现在把变化过程做成一个树的结构，由某一个字符串变化而来的字符串就成为该字符串的子树。参看下图的例子，我们可以得到以下几点结论：

BFS层次遍历：

1.从开始结点出发，设置一个存放当前节点的列表和一个保存下一个节点的列表，一层一层遍历寻找。

2.设置深度（代表替换次数）

3.从当前节点列表中的节点开始替换，比如hit开始，对hit的每一个字符替换成26种可能的结果，如果存在词典中，则加入下一个元素列表nextword中，并删除词典中的该词（避免重复查找）。

4.进入下一层，更新层数（层数代表替换次数），将当前curword替换成下一个元素列表nextword，nextword再置为空。

5.如果遇到当前词的列表中出现了endword，则返回层数。

代码：

 

#https://blog.csdn.net/qqxx6661/article/details/78509871
#127 BFS
class Solution(object):def ladderLength(self, beginWord, endWord, wordList):wordset = set(wordList)curword = [beginWord]nextword = []depth = 1n = len(beginWord)while curword:for item in curword:if item == endWord:return depthfor i in range(n): #因为每个单词长度一样for c in "abcdefghijklmnopqrstuvwxyz":word = item[:i]+c+item[i+1:]if word in wordset:wordset.remove(word)nextword.append(word)depth = depth + 1curword = nextwordnextword = []return 0

 

这篇关于Leet Code OJ 127. Word Ladder [Difficulty: Medium]-python的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---