642. Design Search Autocomplete System

1import java.util.ArrayList;
2import java.util.List;
3import java.util.PriorityQueue;
4
5class Trie {
6    Trie[] children = new Trie[27]; // 26 English letters and 1 space
7    int frequency;
8    String word = "";
9
10    // Inserts a word into the trie with its associated frequency
11    void insert(String word, int frequency) {
12        Trie node = this;
13        for (char ch : word.toCharArray()) {
14            int index = ch == ' ' ? 26 : ch - 'a'; // Convert char to index, space represented by 26
15            if (node.children[index] == null) {
16                node.children[index] = new Trie();
17            }
18            node = node.children[index];
19        }
20        node.frequency += frequency; // Update the frequency of the node (word-end)
21        node.word = word;
22    }
23
24    // Searches for a node with a given prefix in the trie
25    Trie search(String prefix) {
26        Trie node = this;
27        for (char ch : prefix.toCharArray()) {
28            int index = ch == ' ' ? 26 : ch - 'a';
29            if (node.children[index] == null) {
30                return null;
31            }
32            node = node.children[index];
33        }
34        return node;
35    }
36}
37
38class AutocompleteSystem {
39    private Trie rootTrie = new Trie(); // Trie root
40    private StringBuilder currentInput = new StringBuilder();
41
42    // Constructor which takes an array of sentences and their corresponding
43    // frequencies to build the trie
44    public AutocompleteSystem(String[] sentences, int[] times) {
45        for (int i = 0; i < sentences.length; i++) {
46            rootTrie.insert(sentences[i], times[i]);
47        }
48    }
49
50    // Processes input character by character to autocomplete
51    public List<String> input(char inputChar) {
52        List<String> autocompleteResult = new ArrayList<>();
53        if (inputChar == '#') {
54            rootTrie.insert(currentInput.toString(), 1); // Insert the current input into the trie
55            currentInput = new StringBuilder(); // Reset builder for next input
56            return autocompleteResult; // Autocomplete list is empty for new input
57        }
58        currentInput.append(inputChar); // Adding new character to current input
59        Trie node = rootTrie.search(currentInput.toString());
60        if (node == null) {
61            return autocompleteResult; // If no node found, return empty list
62        }
63        PriorityQueue<Trie> minHeap
64            = new PriorityQueue<>((a, b) -> a.frequency == b.frequency ? b.word.compareTo(a.word) : a.frequency - b.frequency);
65        depthFirstSearch(node, minHeap);
66        while (!minHeap.isEmpty()) {
67            autocompleteResult.add(0, minHeap.poll().word);
68        }
69        return autocompleteResult; // Return the list of autocompleted words
70    }
71
72    // DFS to find all words with the same prefix, use a priority queue to sort them based on frequency and lexicographical order
73    private void depthFirstSearch(Trie node, PriorityQueue<Trie> minHeap) {
74        if (node == null || minHeap.size() > 3 && node.frequency < minHeap.peek().frequency) {
75            return; // Early return condition to prune the search
76        }
77        if (node.frequency > 0) {
78            minHeap.offer(node); // If it's a word, offer to the min-heap
79            if (minHeap.size() > 3) {
80                minHeap.poll(); // Keep the size of min-heap no larger than 3
81            }
82        }
83        for (Trie childNode : node.children) {
84            depthFirstSearch(childNode, minHeap); // Recursively search children
85        }
86    }
87}
88
89/**
90 * Your AutocompleteSystem object will be instantiated and called as such:
91 * AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
92 * List<String> param_1 = obj.input(c);
93 */
94

1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <queue>
5
6using namespace std;
7
8// Trie node structure
9class Trie {
10public:
11    unordered_map<char, Trie*> children;
12    int frequency;
13    string word;
14
15    // Constructor
16    Trie() : frequency(0), word("") {}
17
18    // Destructor
19    ~Trie() {
20        for(auto child : children) {
21            delete child.second;
22        }
23    }
24
25    // Inserts a word into the trie with its associated frequency
26    void insert(string word, int frequency) {
27        Trie* node = this;
28        for (char ch : word) {
29            if (node->children.find(ch) == node->children.end())
30                node->children[ch] = new Trie();
31          
32            node = node->children[ch];
33        }
34        node->frequency += frequency; // Update the frequency of the node (word-end)
35        node->word = word;
36    }
37
38    // Searches for a node with a given prefix in the trie
39    Trie* search(string prefix) {
40        Trie* node = this;
41        for (char ch : prefix) {
42            if (node->children.find(ch) == node->children.end())
43                return nullptr;
44          
45            node = node->children[ch];
46        }
47        return node;
48    }
49};
50
51// AutocompleteSystem class to provide autocomplete functionality
52class AutocompleteSystem {
53private:
54    Trie* root Trie;
55    string currentInput;
56
57    // Comparator for priority queue
58    struct TrieComparator {
59        bool operator()(Trie* a, Trie* b) {
60            if(a->frequency == b->frequency) return a->word > b->word;
61            return a->frequency < b->frequency;
62        }
63    };
64
65public:
66    // Constructor which takes a vector of sentences and their corresponding frequencies to build the trie
67    AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
68        rootTrie = new Trie();
69        for (int i = 0; i < sentences.size(); i++) {
70            rootTrie->insert(sentences[i], times[i]);
71        }
72    }
73
74    // Destructor to safely delete the Trie
75    ~AutocompleteSystem() {
76        delete rootTrie;
77    }
78
79    // Processes input character by character to autocomplete
80    vector<string> input(char inputChar) {
81        if (inputChar == '#') {
82            rootTrie->insert(currentInput, 1); // Insert the current input into the trie
83            currentInput.clear(); // Reset builder for next input
84            return vector<string>(); // Return empty vector
85        }
86
87        currentInput += inputChar; // Adding new character to current input
88        Trie* node = rootTrie->search(currentInput);
89        if (!node) {
90            return vector<string>(); // If no node found, return empty list
91        }
92
93        priority_queue<Trie*, vector<Trie*>, TrieComparator> minHeap;
94        depthFirstSearch(node, minHeap);
95
96        vector<string> autocompleteResult;
97        while (!minHeap.empty() && autocompleteResult.size() < 3) {
98            autocompleteResult.insert(autocompleteResult.begin(), minHeap.top()->word);
99            minHeap.pop();
100        }
101        return autocompleteResult; // Return the list of autocompleted words
102    }
103
104private:
105    // DFS to find all words with the same prefix, use a priority queue to sort them based on frequency and lexical order
106    void depthFirstSearch(Trie* node, priority_queue<Trie*, vector<Trie*>, TrieComparator>& minHeap) {
107        if (!node) return;
108        if (node->frequency > 0) {
109            minHeap.push(node); // If it's a word, add it to the min-heap
110            if (minHeap.size() > 3) minHeap.pop(); // If more than 3 elements, remove the one with the lowest frequency
111        }
112        for (auto pair : node->children) {
113            depthFirstSearch(pair.second, minHeap); // Recursively search children
114        }
115    }
116};
117
118// Usage example (not part of the class definition)
119/*
120int main() {
121    vector<string> sentences = {"i love you", "island", "iroman", "i love leetcode"};
122    vector<int> times = {5, 3, 2, 2};
123    AutocompleteSystem obj(sentences, times);
124    vector<string> param_1 = obj.input('i');
125    // Continue processing input characters...
126    return 0;
127}
128*/
129

1// Define the structure of a Trie node
2type TrieNode = {
3  children: TrieNode[];
4  frequency: number;
5  word: string;
6};
7
8// Initialize the root Trie node with 27 children for 26 letters and one space
9let rootTrie: TrieNode = createTrieNode();
10
11// Function to create a new Trie node
12function createTrieNode(): TrieNode {
13  return {
14    children: new Array(27).fill(null), // Initialize an array of 27 null children
15    frequency: 0,
16    word: ""
17  };
18}
19
20// Inserts a word into the trie with its associated frequency
21function insert(word: string, frequency: number): void {
22  let node = rootTrie;
23  for (let ch of word) {
24    const index = ch === ' ' ? 26 : ch.charCodeAt(0) - 'a'.charCodeAt(0);
25    if (node.children[index] === null) {
26      node.children[index] = createTrieNode();
27    }
28    node = node.children[index];
29  }
30  node.frequency += frequency; 
31  node.word = word;
32}
33
34// Searches for a node with a given prefix in the trie
35function search(prefix: string): TrieNode | null {
36  let node = rootTrie;
37  for (let ch of prefix) {
38    const index = ch === ' ' ? 26 : ch.charCodeAt(0) - 'a'.charCodeAt(0);
39    if (node.children[index] === null) {
40      return null;
41    }
42    node = node.children[index];
43  }
44  return node;
45}
46
47// Current input buffer
48let currentInput: string[] = [];
49
50// Autocomplete system constructor mimicking
51function autocompleteSystem(sentences: string[], times: number[]): void {
52  for (let i = 0; i < sentences.length; i++) {
53    insert(sentences[i], times[i]);
54  }
55}
56
57// Processes input character by character to autocomplete
58function input(inputChar: string): string[] {
59  let autocompleteResult: string[] = [];
60  if (inputChar === '#') {
61    insert(currentInput.join(''), 1); // Construct the current input string and insert it into the trie
62    currentInput = []; // Reset current input for next input
63    return autocompleteResult; // Autocomplete list is empty for new input
64  }
65  currentInput.push(inputChar); // Add new character to current input
66  const node = search(currentInput.join(''));
67  if (node === null) {
68    return autocompleteResult; // If no node found, return empty list
69  }
70
71  // Create a min-heap priority queue to store TrieNode elements
72  const minHeap: TrieNode[] = [];
73  depthFirstSearch(node, minHeap);
74  while (minHeap.length) {
75    const nextItem = minHeap.shift();
76    if (nextItem) autocompleteResult.push(nextItem.word);
77  }
78  return autocompleteResult; // Return the list of autocompleted words
79}
80
81// DFS to find all words with the same prefix
82function depthFirstSearch(node: TrieNode, minHeap: TrieNode[]): void {
83  if (!node || (minHeap.length > 2 && node.frequency < minHeap[0].frequency)) {
84    return; // Stop searching if conditions are met
85  }
86  if (node.frequency > 0) {
87    minHeap.push(node); // If the node is a word, push it to the min-heap
88    minHeap.sort((a, b) => b.frequency - a.frequency || a.word.localeCompare(b.word)); // Sort by frequency and lex order
89    if (minHeap.length > 3) {
90      minHeap.shift(); // Remove the lowest frequency node if the heap size is greater than 3
91    }
92  }
93  for (let childNode of node.children) {
94    if (childNode) {
95      depthFirstSearch(childNode, minHeap); // Recursively search all children
96    }
97  }
98}
99
100/**
101 * Example usage:
102 * autocompleteSystem(["i love you", "island", "ironman", "i love leetcode"], [5, 3, 2, 2]);
103 * console.log(input('i')); // Expected autocomplete results for prefix 'i'
104 * console.log(input('#')); // Completing the input and expecting empty result for new input
105 */
106