LeetCode 720 - Longest Word in Dictionary

https://leetcode.com/problems/longest-word-in-dictionary/description/

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:

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:

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].

https://zhanghuimeng.github.io/post/leetcode-720-longest-word-in-dictionary/

因为字符串数量只有1000，长度只有30，所以完全可以采用枚举的方法：先把所有字符串排序（这样可以保证每个字符串的前缀都排在它前面），按顺序把满足要求的字符串加入到一个set中；对于每个字符串，检查它的substr(1, length-1)子串是否包含在set中，如果是则满足要求。（所以里面也含有一些动态规划的思想）这一做法和题解中给出的做法相比有些差异，更类似于[1]，复杂度（假设在HashSet中插入和查询字符串的时间正比于字符串长度）大约是$O(n * \log{(n)} + \sum w_i)$。

如果数据量更大的话，更好的方法是使用Trie。把所有的字符串都插入到一棵Trie中，然后通过DFS或BFS找到最长的连续路径。这样复杂度只有$O(\sum w_i)$。

X. Trie + BFS
https://leetcode.com/problems/longest-word-in-dictionary/discuss/109113/Java-Solution-with-Trie-%2B-BFS

The idea is simple. First, we construct a trie for the dictionary. Then we traverse the whole trie to get the longest word.
We could choose DFS or BFS to achieve the trie traversal. Here, I leverage the property of BFS that it would get a layer of a tree from top to down at one time. Therefore, every time we get a new candidate word, we could replace the old one. Also, I scan the children of a trie node from last to first because we want the word with the smallest lexicographical order.

    class TrieNode {
        TrieNode[] children;
        boolean isWord;
        String word;
        
        public TrieNode() {
            children = new TrieNode[26];
        }
    }
    
    class Trie {
        private TrieNode root;
        
        public Trie() {
            root = new TrieNode();
        }
        
        public void insert(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                int idx = word.charAt(i) - 'a';
                if (node.children[idx] == null) {
                    node.children[idx] = new TrieNode();
                }
                node = node.children[idx];
            }
            node.isWord = true;
            node.word = word;
        }
        
        public String findLongestWord() {
            String result = null;
            Queue<TrieNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TrieNode node = queue.poll();
                    for (int j = 25; j >= 0; j--) {
                        if (node.children[j] != null && node.children[j].isWord) {
                            result = node.children[j].word;
                            queue.offer(node.children[j]);
                        }
                    }
                }
            }
            return result;
        }
    }
    
    public String longestWord(String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        
        return trie.findLongestWord();
    }

X. Trie + DFS
https://zxi.mytechroad.com/blog/string/leetcode-720-longest-word-in-dictionary/
Trie + Sorting

    Trie(): root_(new TrieNode()) {}

    

    void insert(const string& word) {

        TrieNode* p = root_.get();

        for (const char c : word) {

            if (!p->children[c - 'a'])

                p->children[c - 'a'] = new TrieNode();

            p = p->children[c - 'a'];

        }

        p->is_word = true;

    }

    

    bool hasAllPrefixes(const string& word) {

        const TrieNode* p = root_.get();

        for (const char c : word) {

            if (!p->children[c - 'a']) return false;

            p = p->children[c - 'a'];

            if (!p->is_word) return false;

        }

        return true;

    }    

private:

    struct TrieNode {

        TrieNode():is_word(false), children(26, nullptr){}

        

        ~TrieNode() {

            for (auto node : children)

                delete node;

        }

        

        bool is_word;

        vector<TrieNode*> children;

    };

    

    std::unique_ptr<TrieNode> root_;

};

 

class Solution {

public:

    string longestWord(vector<string>& words) {

        std::sort(words.begin(), words.end(),

          [](const string& w1, const string& w2){

            if (w1.length() != w2.length())

                return w1.length() > w2.length();

            return w1 < w2;

          });

            

        Trie trie;

        for (const string& word : words)

            trie.insert(word);

                

        for (const string& word : words)

            if (trie.hasAllPrefixes(word)) return word;  

        

        return "";

    }

Trie + No Sort

    string longestWord(vector<string>& words) {

        Trie trie;

        for (const string& word : words)

            trie.insert(word);

        

        string best;

        for (const string& word : words) {

            if (word.length() < best.length()

            || (word.length() == best.length() && word > best))

                continue;

            if (trie.hasAllPrefixes(word))

                best = word;

        }

        

        return best;

    }

https://leetcode.com/problems/longest-word-in-dictionary/discuss/112720/JAVA-16ms-(99)-@-20180108-Trie+DFS:-clean-easy-explained-and-illustrated

Build a trie in the normal way, then do a dfs to find the longest continuous downward path from the root. This is not a particularly hard question in the context of trie, the point of this solution is to present a generic way of trie building and inserting that can be easily adapted to similar questions. 

• Time Complexity: $O(\sum w_i)$, where $w_i$ is the length of words[i]. This is the complexity to build the trie and to search it.

If we used a BFS instead of a DFS, and ordered the children in an array, we could drop the need to check whether the candidate word at each node is better than the answer, by forcing that the last node visited will be the best answer.

• Space Complexity: $O(\sum w_i)$, the space used by our trie.

    public String longestWord(String[] words) {
        Trie trie = new Trie();
        int index = 0;
        for (String word: words) {
            trie.insert(word, ++index); //indexed by 1
        }
        trie.words = words;
        return trie.dfs();
    }
class Node {
    char c;
    HashMap<Character, Node> children = new HashMap();
    int end;
    public Node(char c){
        this.c = c;
    }
}

class Trie {
    Node root;
    String[] words;
    public Trie() {
        root = new Node('0');
    }

    public void insert(String word, int index) {
        Node cur = root;
        for (char c: word.toCharArray()) {
            cur.children.putIfAbsent(c, new Node(c));
            cur = cur.children.get(c);
        }
        cur.end = index;
    }

    public String dfs() {
        String ans = "";
        Stack<Node> stack = new Stack();
        stack.push(root);
        while (!stack.empty()) {
            Node node = stack.pop();
            if (node.end > 0 || node == root) {
                if (node != root) {
                    String word = words[node.end - 1];
                    if (word.length() > ans.length() ||
                            word.length() == ans.length() && word.compareTo(ans) < 0) {
                        ans = word;
                    }
                }
                for (Node nei: node.children.values()) {
                    stack.push(nei);
                }
            }
        }
        return ans;
    }

public String longestWord(String[] words) {

  Arrays.sort(words, (s1, s2) -> {

    if (s1.length() == s2.length())

      return s1.compareTo(s2);

    return Integer.compare(s1.length(), s2.length());

  });

  Trie trie = new Trie();

  String lw = "";

  for (String word : words) {

    if (trie.insert(word)) {

      if (lw.length() < word.length()) {

        lw = word;

      }

    }

    // System.out.println(trie);

  }

  return lw;

}

private static class TrieNode {

  public TrieNode[] children = new TrieNode[26];

  private boolean isEnd;

  @Override

  public String toString() {

    return "TrieNode [children=" + Arrays.toString(children) + ", isEnd=" + isEnd + "]";

  }

}

private static class Trie {

  private TrieNode root = new TrieNode();

  public boolean insert(String word) {

    TrieNode cur = root;

    boolean isComposed = true;

    for (int i = 0; i < word.length(); i++) {

      char ch = word.charAt(i);

      TrieNode child = cur.children[ch - 'a'];

      if (child == null) {

        if (i != word.length() - 1) {

          isComposed = false;

        }

        child = new TrieNode();

        cur.children[ch - 'a'] = child;

      } else {

        if (i != word.length() - 1 && !child.isEnd) {

          isComposed = false;

        }

      }

      cur = child;

    }

    cur.isEnd = true;

    return isComposed;

  }

  @Override

  public String toString() {

    return "Trie [root=" + root + "]";

  }

}

X. Pre-Sort + DP
https://leetcode.com/problems/longest-word-in-dictionary/discuss/109114/JavaC++-Clean-Code
Time complexity of this approach is O(nlognL) where n is the length of the list and L is the average length of a word, because we cannot just assume comparing two strings here is constant time. However, trie based approach takes O(n*L) time

    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> built = new HashSet<String>();
        String res = "";
        for (String w : words) {
            if (w.length() == 1 || built.contains(w.substring(0, w.length() - 1))) {
                res = w.length() > res.length() ? w : res;
                built.add(w);
            }
        }
        return res;
    }




X.
https://leetcode.com/articles/longest-word-in-dictionary/

For each word, check if all prefixes word[:k] are present. We can use a Set structure to check this quickly.

Whenever our found word would be superior, we check if all it's prefixes are present, then replace our answer.

Alternatively, we could have sorted the words beforehand, so that we know the word we are considering would be the answer if all it's prefixes are present.

• Time complexity : $O(\sum w_i^2)$, where $w_i$ is the length of words[i]. Checking whether all prefixes of words[i] are in the set is $O(\sum w_i^2)$.
• Space complexity : $O(\sum w_i^2)$ to create the substrings.

    public String longestWord(String[] words) {
        Set<String> wordset = new HashSet();
        for (String word: words) wordset.add(word);
        Arrays.sort(words, (a, b) -> a.length() == b.length()
                    ? a.compareTo(b) : b.length() - a.length());
        for (String word: words) {
            boolean good = true;
            for (int k = 1; k < word.length(); ++k) {
                if (!wordset.contains(word.substring(0, k))) {
                    good = false;
                    break;
                }
            }
            if (good) return word;
        }

        return "";
    }

    public String longestWord(String[] words) {
        String ans = "";
        Set<String> wordset = new HashSet();
        for (String word: words) wordset.add(word);
        for (String word: words) {
            if (word.length() > ans.length() ||
                    word.length() == ans.length() && word.compareTo(ans) < 0) {
                boolean good = true;
                for (int k = 1; k < word.length(); ++k) {
                    if (!wordset.contains(word.substring(0, k))) {
                        good = false;
                        break;
                    }
                }
                if (good) ans = word;
            }    
        }
        return ans;
    }