世界上最长的单词是什么（最长的单词是哪个）

题目

给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。

若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。

示例：输入： ["cat","banana","dog","nana","walk","walker","dogwalker"] 输出： "dogwalker"

解释： "dogwalker"可由"dog"和"walker"组成。

提示：0 <= len(words) <= 200

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

解题思路分析

1、排序+递归；时间复杂度O(n^2)，空间复杂度O(n)

var m map[string]boolfunc longestWord(words []string) string {   m = make(map[string]bool)   n := len(words)   for i := 0; i < n; i++ {      m[words[i]] = true   }   sort.Slice(words, func(i, j int) bool {      if len(words[i]) == len(words[j]) {         return words[i] < words[j]      }      return len(words[i]) > len(words[j])   })   for i := 0; i < n; i++ { // 从最长最小字典序的开始找      m[words[i]] = false      if dfs(words[i]) == true {         return words[i]      }   }   return ""}func dfs(str string) bool {   if len(str) == 0 || m[str] == true {      return true   }   for i := 1; i <= len(str); i++ {      subStr := str[:i]      if m[subStr] == true {         if dfs(str[i:]) == true {            return true         }      }   }   return false}

2、排序+动态规划；时间复杂度O(n^3)，空间复杂度O(n)

var m map[string]boolfunc longestWord(words []string) string {   m = make(map[string]bool)   n := len(words)   for i := 0; i < n; i++ {      m[words[i]] = true   }   sort.Slice(words, func(i, j int) bool {      if len(words[i]) == len(words[j]) {         return words[i] < words[j]      }      return len(words[i]) > len(words[j])   })   // 从最长最小字典序的开始找   for i := 0; i < n; i++ {      m[words[i]] = false      if judge(words[i]) == true {         return words[i]      }   }   return ""}// leetcode 139.单词拆分func judge(s string) bool {   dp := make([]bool, len(s)+1)   dp[0] = true   n := len(s)   for i := 1; i <= n; i++ {      for j := 0; j < i; j++ {         if dp[j] == true && m[s[j:i]] == true {            dp[i] = true            break         }      }   }   return dp[n]}

总结

Medium题目，跟leetcode 139.单词拆分类似