SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

A Trie (pronounced as "try") is a tree-like data structure that is used to efficiently store and search strings, particularly when dealing with a large dataset of words or prefixes. The main operations of a trie are inserting a word, searching for a word, and checking if any word starts with a given prefix.

Intuition

The Trie data structure takes advantage of the shared prefixes in a collection of words. Instead of storing each word independently, a Trie stores common prefixes only once, which helps in reducing the overall space and allows for efficient querying.

For instance, the words "apple", "app", and "apply" share the prefix "app". By storing this prefix once and extending from it, we can quickly check for any word that starts with "app" and differentiate between these words efficiently.

Approach

1. Initialization: Create a Trie class with two sets: one for storing complete words (data) and another for storing all possible prefixes (prefs).
2. Insert:
   • For each word, add every prefix of the word to the prefs set.
   • Add the complete word to the data set.
3. Search:
   • Check if the word exists in the data set.
4. StartsWith:
   • Check if the prefix exists in the prefs set.

The operations are based on set lookups, which are average O(1) in complexity.

Complexity

Insert Operation:

O(n), where n is the length of the word being inserted. This is because we need to create and store every prefix of the word.

Search Operation:

O(1) on average due to the set lookup.

StartsWith Operation:

O(1) on average due to the set lookup.

Space Complexity:

O(m * n), where m is the number of words and n is the average length of the words. This is because we store all the words and their prefixes.

Code

C++

class Trie {
public:
    Trie() {
        // Initialization of the Trie
    }
    void insert(std::string word) {
        std::string cur = "";
        for (char c : word) {
            cur += c;
            prefs.insert(cur);
        }
        data.insert(word);
    }
    
    bool search(std::string word) {
        return data.find(word) != data.end();
    }
    
    bool startsWith(std::string prefix) {
        return prefs.find(prefix) != prefs.end();
    }

private:
    std::unordered_set<std::string> data;
    std::unordered_set<std::string> prefs;
};

Python

class Trie:

    def __init__(self):
        self.data = set()
        self.prefs = set()

    def insert(self, word: str) -> None:
        cur = ''
        for char in word:
            cur += char
            self.prefs.add(cur)
        self.data.add(word)

    def search(self, word: str) -> bool:
        return word in self.data

    def startsWith(self, prefix: str) -> bool:
        return prefix in self.prefs

Java

class Trie {
    private HashSet<String> data;
    private HashSet<String> prefs;

    public Trie() {
        data = new HashSet<>();
        prefs = new HashSet<>();
    }
    
    public void insert(String word) {
        StringBuilder cur = new StringBuilder();
        for (int i = 0; i < word.length(); i++) {
            cur.append(word.charAt(i));
            prefs.add(cur.toString());
        }
        data.add(word);
    }
    
    public boolean search(String word) {
        return data.contains(word);
    }
    
    public boolean startsWith(String prefix) {
        return prefs.contains(prefix);
    }
}

JavaScript

class Trie 
{
    constructor() {
        this.data = new Set()
        this.prefs = new Set()
    }
    insert(w) {
        let cur = ''
        for (let i = 0; i < w.length; i++) {
            cur += w[i]
            this.prefs.add(cur)
        }
        this.data.add(w)

    }
    search(w) {
        return this.data.has(w)
    }
    startsWith(pref) {
        return this.prefs.has(pref)
    }
}