单词转换

Posted by Jason on Monday, February 10, 2020

TOC

题目

给定字典中的两个词,长度相等。写一个方法,把一个词转换成另一个词, 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。

编写一个程序,返回一个可能的转换序列。如有多个可能的转换序列,你可以返回任何一个。

示例 1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出:
["hit","hot","dot","lot","log","cog"]
示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: []

解释: endWord "cog" 不在字典中,所以不存在符合要求的转换序列。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/word-transformer-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

题目中判断某个单词是否可以转换成另一个单词,每次变换单词之间只能修改一个字符,所以,可以将两个单词之间是否可以转换,换一种表述方式就是两个单词是否相邻。这样整个单词表可以转化成为一个图结构。单词之间是否能够转换,就是求图中两点间是否连通。

代码

func findLadders(beginWord string, endWord string, wordList []string) []string {
	adjW := make(map[int][]int)
	wrdNum := len(wordList)
	path := []string{}

	start := -1
	end := -1
	// build word adjacent map
        // @TODO 循环逻辑优化
	for k, v := range wordList {
		adj := make([]int, 0, wrdNum)
		for i := 0; i < wrdNum; i++ {
			if i == k {
				continue
			}
			word := wordList[i]
			notMatch := false
			for j, c := range word {
				if v[j] != byte(c) {
					if notMatch {
						notMatch = false
						break
					}
					notMatch = true
				}
			}

			if notMatch {
				adj = append(adj, i)
			}
		}

		adjW[k] = adj
		if v == beginWord {
			start = k
		}

		if v == endWord {
			end = k
		}
	}
	if end < 0 {
		return path
	}

        // @TODO 和上面邻接表合并
	if start < 0 {
		adj := []int{}
		for k, w := range wordList {
			notMatch := false
			for j, c := range w {
				if byte(c) != beginWord[j] {
					if notMatch {
						notMatch = false
						break
					}
					notMatch = true
				}
			}

			if notMatch {
				adj = append(adj, k)
			}
		}

		start = wrdNum
		adjW[start] = adj
		wordList = append(wordList, beginWord)
	}

	adj, exit := adjW[start]
	if !exit || len(adj) < 1 {
		return path
	}

	kpath := BFSSearch(start, end, adjW)
	if len(kpath) < 2 {
		return path
	}

	for i := len(kpath) - 1; i > -1; i-- {
		key := kpath[i]
		path = append(path, wordList[key])
	}

	return path
}

func BFSSearch(start, end int, wrdMap map[int][]int) []int {
	list := []int{start}
	hasSearched := map[int]int{start: -1}
	path := []int{}

loop:
	for i := 0; i < len(list); i++ {
		w := list[i]

		adjs := wrdMap[w]
		for _, adj := range adjs {
			if _, exit := hasSearched[adj]; !exit {
				hasSearched[adj] = w
				if adj == end {
					break loop
				}
				list = append(list, adj)
			}
		}

	}

	pre := end
	for pre > -1 {
		var exit bool
		path = append(path, pre)
		pre, exit = hasSearched[pre]
        fmt.Println(pre, exit)
		if !exit {
			return path
		}
	}

	return path
}

「真诚赞赏,手留余香」

Jason Blog

真诚赞赏,手留余香

使用微信扫描二维码完成支付


comments powered by Disqus