Skip to content

17.15. Longest Word

Description

Given a list of words, write a program to find the longest word made of other words in the list. If there are more than one answer, return the one that has smallest lexicographic order. If no answer, return an empty string.

Example: 


Input:  ["cat","banana","dog","nana","walk","walker","dogwalker"]

Output:  "dogwalker"

Explanation:  "dogwalker" can be made of "dog" and "walker".

Note:

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

Solutions

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

    def insert(self, word):
        node = self
        for c in word:
            idx = ord(c) - ord(