导航：首页 > 互联网科技 >

golang刷leetcode技巧之如何实现最长单词

发表于：2025-02-04 作者：千家信息网编辑

千家信息网最后更新 2025年02月04日，这篇文章主要为大家展示了"golang刷leetcode技巧之如何实现最长单词"，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下"golang刷leetcode

千家信息网最后更新 2025年02月04日golang刷leetcode技巧之如何实现最长单词

这篇文章主要为大家展示了"golang刷leetcode技巧之如何实现最长单词"，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下"golang刷leetcode技巧之如何实现最长单词"这篇文章吧。

给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。

示例：

输入： ["cat","banana","dog","nana","walk","walker","dogwalker"]
输出： "dogwalker"
解释： "dogwalker"可由"dog"和"walker"组成。

提示：

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

解题思路

1，排序＋map

2，从最长到最短，

3，深度优先搜索，找剩余的单词是否匹配

4，需要注意的是，搜索前要把当前单词从map删除

5，但是要配合长度递减排序

代码实现

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}