面试题 17.15. 最长单词

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

示例：

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

提示：

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

Python 解答：
1.DFS+集合，可用前缀树优化

class Solution:
    class Trie:
        class Node:
            def __init__(self):
                self.node = {}
                self.isword = False

        def __init__(self):
            self.root = self.Node()

        def add(self, word):
            cur = self.root
            for c in word:
                if c not in cur.node.keys():
                    cur.node[c] = self.Node()
                cur = cur.node[c]
            cur.isword = True

        def search(self, word):
            cur = self.root
            for c in word:
                if c not in cur.node.keys():
                    return False
                cur = cur.node[c]
            return cur.isword

    def longestWord(self, words: List[str]) -> str:
        words.sort(key=(lambda x: (-len(x), x)))
        print(words)
        aset = set(words)
        def dfs(word, c):
            if not word and c >1:
                return True
            elif not word and c <= 1:
                return False
            else:
                temp = []
                for i in range(1, len(word)+1):
                    if word[:i] in aset:
                        temp.append(i)
                if not temp:
                    return False
                res = False
                for j in temp:
                    # res = res or dfs(word[j:], c+1)
                    if res:
                        return True
                    res = dfs(word[j:], c+1)
                return res
        for word in words:
            if dfs(word, 0):
                return word
        return ""