golang刷leetcode技巧之如何實現(xiàn)最長單詞

發(fā)布時間：2021-12-15 09:55:18 來源：億速云閱讀：158 作者：小新欄目：大數(shù)據(jù)

這篇文章主要為大家展示了“golang刷leetcode技巧之如何實現(xiàn)最長單詞”，內(nèi)容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“golang刷leetcode技巧之如何實現(xiàn)最長單詞”這篇文章吧。

給定一組單詞words，編寫一個程序，找出其中的最長單詞，且該單詞由這組單詞中的其他單詞組合而成。若有多個長度相同的結(jié)果，返回其中字典序最小的一項，若沒有符合要求的單詞則返回空字符串。

示例：

輸入： ["cat","banana","dog","nana","walk","walker","dogwalker"]
輸出： "dogwalker"
解釋： "dogwalker"可由"dog"和"walker"組成。

提示：

0 <= len(words) <= 100
1 <= len(words[i]) <= 100

解題思路

1，排序＋map

2，從最長到最短，

3，深度優(yōu)先搜索，找剩余的單詞是否匹配

4，需要注意的是，搜索前要把當前單詞從map刪除

5，但是要配合長度遞減排序

代碼實現(xiàn)

import "sort"
type sortWords []string
func(s sortWords) Len() int {    return len(s)}
func(s sortWords) Swap(i, j int) {    s[i], s[j] = s[j], s[i]}
func(s sortWords) Less(i, j int) bool {    return len(s[i]) >= len(s[j])}
func longestWord(words []string) string {    longest := 0    wordsMap := make(map[string]bool)
    for _, word := range words {        wordsMap[word] = true        if longest < len(word) {            longest = len(word)        }    }    sort.Sort(sortWords(words))    fmt.Println(words)    for _, word := range words {        delete(wordsMap, word)        if dfs(word, wordsMap) {            return word         }    }    return "" }
func dfs(word string, wordsMap map[string]bool) bool {    if word == "" {        return true    }    for i := 1; i <= len(word); i++ {        if _, ok := wordsMap[word[:i]];ok {            if dfs(word[i:], wordsMap) {                return true            }        }    }    return false}

以上是“golang刷leetcode技巧之如何實現(xiàn)最長單詞”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業(yè)資訊頻道！

向AI問一下細節(jié)

golang刷leetcode技巧之如何實現(xiàn)最長單詞

猜你喜歡

最新資訊

相關推薦

相關標簽