leetcode-720-Longest-Word-in-Dictionary

发表于   |  

描述

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

1
2
3
4
5
Input: 
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation: 
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

1
2
3
4
5
Input: 
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: 
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Note:

All the strings in the input will only contain lowercase letters.

The length of words will be in the range [1, 1000].

The length of words[i] will be in the range [1, 30].

分析

题意是从一个字符串的列表中找到最长的那个单词，如果长度一样，按照字母顺序排序，有一个额外的要求是这个单词必须有某个前缀也在字符串列表中。可以先排个序，这样的话就不用考虑字典顺了，接着再进行一次遍历，只不过遍历的时候需要判断前缀也在给定的字符串列表里。也可以使用前缀树，用空间换时间，时间复杂度是 $O(n)$

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        HashSet set = new HashSet();
        String result = "";
        for (String word: words) {
            if (word.length() == 1 || set.contains(word.substring(0, word.length()-1))) {
                set.add(word);
                if (word.length() > result.length()) {
                    result = word;
                }
            }
        }
        return result;
    }
}

解决方案2(Java)

从 Solution 里『借鉴』了一下代码。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    public String longestWord(String[] words) {
        Trie trie = new Trie();
        int index = 0;
        for (String word: words) {
            trie.insert(word, ++index);
        }
        trie.words = words;
        return trie.dfs();
    }
}

class TrieNode {
    char c;
    HashMap<Character, TrieNode> children = new HashMap();
    int end;
    public TrieNode(char c) {
        this.c = c;
    }
}

class Trie {
    TrieNode root;
    String[] words;
    
    public Trie() {
        root = new TrieNode('0');
    }
    
    public void insert(String word, int index) {
        TrieNode cur = root;
        for (char c: word.toCharArray()) {
            cur.children.putIfAbsent(c, new TrieNode(c));
            cur = cur.children.get(c);
        }
        cur.end = index;
    }
    
    public String dfs() {
        String result = "";
        Stack<TrieNode> stack = new Stack();
        stack.push(root);
        while (!stack.empty()) {
            TrieNode node = stack.pop();
            if (node.end > 0 || node == root) {
                if (node != root) {
                    String word = words[node.end-1];
                    if (word.length() > result.length() || word.length() == result.length() && word.compareTo(result) < 0) {
                        result = word;
                    }
                }
                for (TrieNode children: node.children.values()) {
                    stack.push(children);
                }
            }
        }
        return result;
    }
}

相关问题

题目来源