題目大意: 給一個開始單詞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:]...)) } } }View Code
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 }