golang刷leetcode 技巧（41）最长单词

golangLeetcode

发布于 2022-08-02 18:48:55

2180

发布于 2022-08-02 18:48:55

给定一组单词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
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-03-28，如有侵权请联系 cloudcommunity@tencent.com 删除

map