欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【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
}

 

上一篇:

下一篇: