当前位置： 移动技术网 > IT编程>脚本编程>Go语言 > 【leetcode】127. Word Ladder

【leetcode】127. Word Ladder

2019年11月18日  | 移动技术网IT编程  | 我要评论

题目大意：

给一个开始单词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
}

 

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网