Trie or HashTable?

Problems like this one can be solved with a Trie or Hashtable. The former is more "elegant" and uses less space, so it is preferred. The latter is an easier implementation (IMO). The following problem was solved using the Hashtable approach: Longest Word With All Prefixes - LeetCode

1858. Longest Word With All Prefixes

Medium

Given an array of strings words, find the longest string in words such that every prefix of it is also in words.

• For example, let words = ["a", "app", "ap"]. The string "app" has prefixes "ap" and "a", all of which are in words.

Return the string described above. If there is more than one string with the same length, return the lexicographically smallest one, and if no string exists, return "".

 

Example 1:

Input: words = ["k","ki","kir","kira", "kiran"]
Output: "kiran"
Explanation: "kiran" has prefixes "kira", "kir", "ki", and "k", and all of them appear in words.

Example 2:

Input: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: Both "apple" and "apply" have all their prefixes in words.
However, "apple" is lexicographically smaller, so we return that.

Example 3:

Input: words = ["abc", "bc", "ab", "qwe"]
Output: ""

 

Constraints:

• 1 <= words.length <= 105
• 1 <= words[i].length <= 105
• 1 <= sum(words[i].length) <= 105

Approach:

1/ Push the words to a Hashtable

2/ For each word, check whether each prefix of the word is in (1)

Since the total number of characters won't exceed 10^5, the execution time becomes 10^5, which is fast. Code is below, cheers, ACC

public class Solution {
    public string LongestWord(string[] words)
    {
        Hashtable cache = new Hashtable();
        foreach (string w in words) 
            if(!cache.ContainsKey(w)) cache.Add(w, true);

        string best = "";
        foreach (string w in words)
        {
            bool found = true;
            for (int i = 1; i <= w.Length; i++)
            {
                if (!cache.ContainsKey(w.Substring(0, i)))
                {
                    found = false;
                    break;
                }
            }
            if (found)
            {
                if (w.Length > best.Length || (w.Length == best.Length && w.CompareTo(best) < 0)) best = w;
            }
        }

        return best;
    }
}