Learning Journal

2/24/2024

Implement Trie (Prefix Tree)

class TrieNode {
    public static readonly HEAD = 0;

    private value:string | 0;
    private nexts: Record<string, TrieNode|null> = {};

    constructor(val:string|0){
        this.value = val;
        
    }

    hasNext(val:string):boolean {
        return this.nexts[val] !== undefined;

    }

    setNext(newNode:TrieNode|null){
        const nextVal = newNode.getValue();
        this.nexts[nextVal] = newNode;
    }


    getNext(val:string):TrieNode {
        return this.nexts[val];
    }
    end() {
        this.nexts["END"] = null;
    }

    isEnd():boolean {
        return this.nexts["END"] !== undefined;
    }

    getValue():string|0 {
        return this.value;
    }
}


class Trie {
    private head: TrieNode;

    constructor() {
        this.head = new TrieNode(TrieNode.HEAD);
        this.head.end();
    }

    insert(word: string): void {
        let curNode = this.head;

        for(let i = 0; i < word.length; i++) {
            if(!curNode.hasNext(word[i])) {
                const newNode = new TrieNode(word[i]);
                curNode.setNext(newNode);
                curNode = newNode;
            }
            else {
                curNode = curNode.getNext(word[i]);
            }

                
        }

        curNode.end();
    }

    search(word: string): boolean {
        let curNode = this.head;

        for(let i = 0; i < word.length; i++) {
            if(!curNode.hasNext(word[i]))
                return false;
            
            curNode = curNode.getNext(word[i]);
        }

        return curNode.isEnd();
    }

    startsWith(prefix: string): boolean {
        let curNode = this.head;

        for(let i = 0; i < prefix.length; i++) {
            if(!curNode.hasNext(prefix[i]))
                return false;
            
            curNode = curNode.getNext(prefix[i]);
        }

        return true;
    }
}


/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

class TrieNode {
    public static readonly HEAD = 0;

    private value:string | 0;
    private nexts: Record<string, TrieNode|null> = {};

    constructor(val:string|0){
        this.value = val;
        
    }

    hasNext(val:string):boolean {
        return this.nexts[val] !== undefined;

    }

    setNext(newNode:TrieNode|null){
        const nextVal = newNode.getValue();
        this.nexts[nextVal] = newNode;
    }


    getNext(val:string):TrieNode {
        return this.nexts[val];
    }
    end() {
        this.nexts["END"] = null;
    }

    isEnd():boolean {
        return this.nexts["END"] !== undefined;
    }

    getValue():string|0 {
        return this.value;
    }
}


class Trie {
    private head: TrieNode;

    constructor() {
        this.head = new TrieNode(TrieNode.HEAD);
        this.head.end();
    }

    insert(word: string): void {
        let curNode = this.head;

        for(let i = 0; i < word.length; i++) {
            if(!curNode.hasNext(word[i])) {
                const newNode = new TrieNode(word[i]);
                curNode.setNext(newNode);
                curNode = newNode;
            }
            else {
                curNode = curNode.getNext(word[i]);
            }

                
        }

        curNode.end();
    }

    search(word: string): boolean {
        let curNode = this.head;

        for(let i = 0; i < word.length; i++) {
            if(!curNode.hasNext(word[i]))
                return false;
            
            curNode = curNode.getNext(word[i]);
        }

        return curNode.isEnd();
    }

    startsWith(prefix: string): boolean {
        let curNode = this.head;

        for(let i = 0; i < prefix.length; i++) {
            if(!curNode.hasNext(prefix[i]))
                return false;
            
            curNode = curNode.getNext(prefix[i]);
        }

        return true;
    }
}


/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

THE PROBLEM

This is my solution for the Trie problem. I used the class TrieNode to represent each node in the Trie. Basically, each node has a value and a hash table to store all nodes that it connects. When search function is called, we traverse along the Trie. If somewhere along the way, we can not find the next node that has the value of the next character, we stop and return false. Otherwise, when we comes to the last character, we check if it has the end mark after it. If it is, we return true.

The catch here is how to add two words that have the same prefix to the trie. I use the "end" marker to denote the end of a word.

Revised by ChatGPT

This solution implements a Trie, a tree-like data structure used for efficient retrieval of strings. The key components are:

TrieNode Class: Represents each node in the Trie. It has a value (the character it represents) and a map (nexts) to store its children nodes. Each node also has a method isEnd to check is it's the end of a word.
Trie Class: Contains the root node (head) and methods for inserting, searching, and checking prefixes: insert(word): Adds a words to the Trie. Iterates through each character of the word, creating new nodes as needed. search(word): Checks if a word exists in the Trie. Traverses the Trie according to the word's characters and returns true if the end of the word is marked. startsWith(prefix): Checks if any word in the Trie starts with the given prefix. Similar to search, but doesn't require the end of the word to be marked.

The solution utilizes an "end" marker (implemented as a null value in nexts with the key "END") to denote the end of a word. This approach allows for efficient differentiation between words with common prefixes.