【leetcode】127. Word Ladder
程序员文章站
2023-12-24 19:13:33
题目大意: 给一个开始单词beginword和一个结束单词endword, 再给一个单词列表wordList。从beginword变换到endword, 每次只能变换一个字母,且变换成的词属于wordList。 解决思路: 其实是个变相的BFS,寻找当前集合中相邻的可以进行变换的单词,更新当前集合, ......
题目大意:
给一个开始单词beginword和一个结束单词endword, 再给一个单词列表wordlist。从beginword变换到endword, 每次只能变换一个字母,且变换成的词属于wordlist。
解决思路:
其实是个变相的bfs,寻找当前集合中相邻的可以进行变换的单词,更新当前集合,直到集合中出现endword。
另,一开始用dfs,递归解法,结果tle。
超时解法:
var isexist = false var minlen = 0 var target = "" func ladderlength(beginword string, endword string, wordlist []string) int { minlen = len(wordlist) target = endword bfs(1, beginword, wordlist) if isexist == false { minlen = 0 } return minlen } func bfs(curlen int, curstr string, remainlist []string) { for i, remainstr := range remainlist { diffnum := 0 for j, curch := range curstr { if byte(curch) != byte(remainstr[j]) { diffnum++ } if diffnum > 1 { break } } if target == curstr { isexist = true if minlen > curlen { minlen = curlen return } } if diffnum == 1 { bfs(curlen + 1, remainstr, append(remainlist[:i], remainlist[i+1:]...)) } } }
bfs:
func ladderlength(beginword string, endword string, wordlist []string) int { var candilist = []string{beginword} var minlen = 1 for len(candilist) > 0 { var templist []string for _, candword := range candilist { if candword == endword { return minlen } for i, word := range wordlist { if word == candword { wordlist = append(wordlist[:i], wordlist[i+1:]...) break } } for _, word := range wordlist { diffnum := 0 for j, ch := range candword { if byte(ch) != byte(word[j]) { diffnum++ } if diffnum > 1 { break } } if diffnum == 1 { templist = append(templist, word) } } } candilist = templist minlen++ } return 0 }
推荐阅读
-
【leetcode】127. Word Ladder
-
LeetCode 139. Word Break (断词)
-
【leetcode】127. Word Ladder
-
C++实现LeetCode(127.词语阶梯)
-
LeetCode 58.Length of Last Word (最后一个单词的长度)
-
LeetCode1003.Check If Word Is Valid After Substitutions(检查替换后的词是否有效)
-
【leetcode】211. Add and Search Word - Data structure design
-
LeetCode-211. Add and Search Word - Data structure design(字典树和递归)
-
Word Ladder
-
Leetcode算法——58、最后单词的长度(length of last word)