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;
        }

    Labels

    LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

    Popular Posts