medium Search Suggestions System

Problem Statement

Given a list of distinct strings products and a string searchWord.

Determine a set of product suggestions after each character of the search word is typed. Every time a character is typed, return a list containing up to three product names from the products list that have the same prefix as the typed string.

If there are more than 3 matching products, return 3 lexicographically smallest products. These product names should be returned in lexicographical (alphabetical) order.

Examples

1. Example 1:

   • Input: Products: ["apple", "apricot", "application"], searchWord: "app"
   • Expected Output: [["apple", "apricot", "application"], ["apple", "apricot", "application"], ["apple", "application"]]
   • Justification: For the perfix 'a', "apple", "apricot", and "application" match. For the prefix 'ap', "apple", "apricot", and "application" match. For the prefix 'app', "apple", and "application" match

2. Example 2:

   • Input: Products: ["king", "kingdom", "kit"], searchWord: "ki"
   • Expected Output: [["king", "kingdom", "kit"], ["king", "kingdom", "kit"]]
   • Justification: All products starting with "k" are "king", "kingdom", and "kit". The list remains the same for the 'ki' prefix.

3. Example 3:

   • Input: Products: ["fantasy", "fast", "festival"], searchWord: "farm"
   • Expected Output: [["fantasy", "fast", "festival"], ["fantasy", "fast"], [], []]
   • Justification: Initially, "fantasy", "fast", and "festival" match 'f'. Moving to 'fa', only "fantasy" and "fast" match. No product matches with "far", and "farm".

Constraints:

• 1 <= products.length <= 1000
• 1 <= products[i].length <= 3000
• 1 <= sum(products[i].length) <= 2 * 10⁴
• All the strings of products are unique.
• products[i] consists of lowercase English letters.
• 1 <= searchWord.length <= 1000
• searchWord consists of lowercase English letters.

Solution

To solve this problem, We will use the trie data structure to store the list of products. The trie is built by inserting each product, where each node represents a character. This structure allows us to efficiently find products that share a common prefix.

After building the trie, we process the search word by checking each of its prefixes. For each prefix, we perform a depth-first search (DFS) starting from the node matching the end of the prefix. The DFS is designed to find up to three lexicographically up to 3 smallest words that start with the given prefix. This approach of using a trie combined with DFS for each prefix ensures that we can quickly and effectively generate the required list of product suggestions.

Step-by-Step Algorithm

1. Build the Trie:

   • Create a root node representing the starting point of the trie.
   • For each product:
     • Start from the root and for each character in the product, navigate to the corresponding child node. Create a new node if it doesn't exist.
     • Mark the node corresponding to the last character of the product as a word end.

2. Process Each Prefix of the Search Word:

   • Initialize an empty list to store the final suggestions for each prefix.
   • For each character in the search word, form a prefix.
     • Start from the root of the trie and navigate to the node corresponding to the last character of the current prefix.
     • If the node for the current prefix doesn't exist, add an empty list to the suggestions and move to the next prefix.

3. DFS for Each Prefix:

   • Upon reaching the node corresponding to the current prefix, perform a DFS.
     • Initialize an empty buffer to store up to three products.
     • Explore all possible paths from the current node. If a path leads to a node marked as a word end, add the corresponding product to the buffer.
     • Stop the DFS when you have collected three products or explored all paths.

4. Compile Suggestions:

   • Add the buffer containing up to three products to the list of suggestions for the current prefix.
   • Continue the process for the next prefix.

Algorithm Walkthrough for Example 3

• Input: Products = ["fantasy", "fast", "festival"], Search Word = "farm"
• Walkthrough:
  1. Building the Trie:
     • Insert "fantasy", "fast", "festival" into the trie, creating nodes for each character.
     • Mark the end of each word in the trie.
  2. Processing Prefixes:
     • Prefix "f": Node exists. Proceed to DFS.
     • Prefix "fa": Node exists. Proceed to DFS.
     • Prefix "far": Node does not exist. Add an empty list to suggestions and skip DFS.
     • Prefix "farm": Node does not exist. Add an empty list to suggestions and skip DFS.
  3. DFS for "f" and "fa":
     • For "f": DFS finds "fantasy", "fast", "festival". Add these to suggestions.
     • For "fa": DFS finds "fantasy", "fast". Add these to suggestions.
  4. Final Output:
     • Suggestions: [["fantasy", "fast", "festival"], ["fantasy", "fast"], [], []].

This walkthrough illustrates how the trie efficiently organizes the products, and the DFS ensures that only the top three lexicographical matches for each prefix are selected.

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// class TrieNode {
//     TrieNode[] children = new TrieNode[26];
//     boolean isEnd = false;
// }

class Trie {

  TrieNode root;

  Trie() {
    root = new TrieNode();
  }

  // Inserts a word into the trie
  void insert(String word) {
    TrieNode node = root;
    for (char ch : word.toCharArray()) {
      if (node.children[ch - 'a'] == null) {
        node.children[ch - 'a'] = new TrieNode();
      }
      node = node.children[ch - 'a'];
    }
    node.isEnd = true;
  }

  // Performs a DFS to find all words with the given prefix
  void dfs(TrieNode node, List<String> list, StringBuilder word) {
    if (list.size() == 3) return; // Limit to 3 suggestions
    if (node.isEnd) {
      list.add(word.toString());
    }

    for (char ch = 'a'; ch <= 'z'; ch++) {
      if (node.children[ch - 'a'] != null) {
        word.append(ch);
        dfs(node.children[ch - 'a'], list, word);
        word.deleteCharAt(word.length() - 1);
      }
    }
  }

  // Searches the trie for words starting with prefix
  List<String> search(String prefix) {
    TrieNode node = root;
    List<String> list = new ArrayList<>();

    for (char ch : prefix.toCharArray()) {
      if (node.children[ch - 'a'] == null) {
        return list; // No words found with this prefix
      }
      node = node.children[ch - 'a'];
    }

    dfs(node, list, new StringBuilder(prefix));
    return list;
  }
}

class Solution {

  public List<List<String>> suggestedProducts(
    String[] products,
    String searchWord
  ) {
    Trie trie = new Trie();
    for (String product : products) {
      trie.insert(product);
    }

    List<List<String>> result = new ArrayList<>();
    StringBuilder prefix = new StringBuilder();

    for (char ch : searchWord.toCharArray()) {
      prefix.append(ch);
      result.add(trie.search(prefix.toString()));
    }

    return result;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Test Example 1
    String[] products1 = { "apple", "apricot", "application" };
    String searchWord1 = "app";
    System.out.println(
      "Example 1: " + solution.suggestedProducts(products1, searchWord1)
    );

    // Test Example 2
    String[] products2 = { "king", "kingdom", "kit" };
    String searchWord2 = "ki";
    System.out.println(
      "Example 2: " + solution.suggestedProducts(products2, searchWord2)
    );

    // Test Example 3
    String[] products3 = { "fantasy", "fast", "festival" };
    String searchWord3 = "farm";
    System.out.println(
      "Example 3: " + solution.suggestedProducts(products3, searchWord3)
    );
  }
}

Time and Space Complexity Analysis

Time Complexity

• Building the Trie: (O(N x L)), where (N) is the number of products and (L) is the average length of the products.
• Searching for Each Prefix: (O(M x K)), where (M) is the length of the search word and (K) is the time taken for the DFS, which is limited to 3 (constant time). Overall, it's approximately (O(M)).

Overall Time Complexity: O(N * L + M), combining the time to build the Trie and perform searches.

Space Complexity

• Trie Storage: (O(N x L)), as each product of average length (L) is stored in the trie.
• Search Results: (O(M)), as we store up to 3 suggestions for each character in the search word.

Overall, the space complexity is dominated by the trie storage, which is (O(N x L)).