Categories
Binary Tree Leetcode Recursion

Is Subtree

let isSubtree = function(mainTree, subTree) {

    function isSame(left, right) {
        if (left === right) return true;
        if (left === null && right !== null) return false;
        if (left !== null && right === null) return false;
        if (left.val !== right.val) return false;
        return isSame(left.left, right.left)
            && isSame(left.right, right.right);
    }

    if (mainTree === subTree) return true;
    if (!mainTree) return false;
    if (isSame(mainTree, subTree)) return true;

    return isSubtree(mainTree.left, subTree) || isSubtree(mainTree.right, subTree);
};
Categories
Array Leetcode Sort

Search Suggestion System (Simple)

let suggestedProducts = function(products, searchWord) {
    products.sort();

    let result = [];
    for(let i = 0; i < searchWord.length; i++) {
        products = products.filter(p => p[i] === searchWord[i]);
        result.push(products.slice(0, Math.min(3, products.length)));
    }

    return result; //?
};
Categories
Breadth First Search Leetcode Recursion Trie

Search Suggestion System (Trie)

let suggestedProducts = function(products, searchWord) {
    const MAX_RESULT_COUNT = 3;
    let root = {
        children: {}
    };

    function addToNode(word, index, node) {
        if (index >= word.length) {
            node.end = true;
            return;
        }
        //
        const child = node.children[word[index]];
        if (child) {
            addToNode(word, index + 1, child);
        }
        else {
            let child = {val: word[index], parent: node, children: {}};
            node.children[word[index]] = child;
            addToNode(word, index + 1, child);
        }
    }

    function getWord(leaf) {
        let node = leaf;
        let str = '';
        while (node) {
            if (node.val) str = node.val + str; //?
            node = node.parent; //?
        }

        return str; //?
    }

    function searchProducts(searchString) {

        let words = [];
        let nodes = [...Object.entries(root.children)], len = searchString.length;
        while (nodes.length) {

            let currentNodeLength = nodes.length;
            while (currentNodeLength > 0) {
                currentNodeLength--;

                const node = nodes.pop();
                const [key, val] = node;
                if (len > 0 && key === searchString[searchString.length - len]) {
                    nodes.unshift(...Object.entries(val.children));

                    if (len === 1 && val.end) {
                        words.push(getWord(val));
                    }
                } else if (len <= 0) {
                    if (val.end) words.push(getWord(val));
                    nodes.unshift(...Object.entries(val.children));
                }
            }
            len--;
        }

        return words.sort().slice(0, Math.min(MAX_RESULT_COUNT, words.length));
    }

    for(let product of products) {
        addToNode(product, 0, root);
    }


    let result = [];
    for (let i = 0; i < searchWord.length; i++) {
        result.push(searchProducts(searchWord.substring(0, i + 1))); //?
    }

    return result; //?
};
Categories
Array Binary Search Leetcode Recursion

Search Matrix

let searchMatrix = function(matrix, target) {
    if(!matrix.length) return false;

    function search(startRow, endRow, startCol, endCol) {
        console.log(startRow, endRow, startCol, endCol);
        let midRow = Math.floor((startRow + endRow) / 2); //?
        let midCol = Math.floor((startCol + endCol) / 2); //?


        if (startRow < endRow && startCol < endCol) {
            const midValue = matrix[midRow][midCol]; //?
            if(midValue === target) {
                return true;
            }
            if (midValue < target) {
                return search(midRow + 1, endRow, startCol, endCol)
                        || search(startRow, endRow, midCol + 1, endCol);
            }
            else {
                return search(startRow, midRow, startCol, endCol)
                    || search(startRow, endRow, startCol, midCol);
            }
        }

        return false;
    }

    return search(0, matrix.length, 0, matrix[0].length);
};
Categories
Array Leetcode String

Top K Frequent Words

let topKFrequent = function(words, k) {
    let map = new Map();
    words.forEach(word => {
        if(map.has(word)) {
            map.set(word, map.get(word) + 1);
        }
        else {
            map.set(word, 1);
        }
    });

    return [...map].sort((x, y) => {
        const f1 = x[1], f2 = y[1]
        if (f1 < f2) return 1;
        if (f1 > f2) return -1;
        return x[0].localeCompare(y[0]);
    }).map(x => x[0]).slice(0, k);
};
Categories
Leetcode String

Most Common Word

let mostCommonWord = function(paragraph, banned) {
    let wordMap = paragraph.toLowerCase()
        .replace(/\W+/g, ' ')
        .trim()
        .split(' ')
        .filter(word => banned.indexOf(word) < 0)
        .reduce((map, y) => {
            if (map.has(y)) {
                map.set(y, map.get(y) + 1);
            }
            else {
                map.set(y, 1);
            }
            return map;
        }, new Map()); //?


    let word = null, count = 0;
    for (let [key, val] of wordMap) {
        if (val > count) {
            count = val;
            word = key;
        }
    }

    return word;
};

Categories
Leetcode

LRU Cache

class LRUCache {
constructor(capacity) {
    this.capacity = capacity;
    this.cache = {};
    this.keys = [];
};

get(key) {
    // if value is already in the cache,
    // reorder keys array and put the key on the end of queue
    let val = this.cache[key];
    if (val !== undefined) {
        this.keys.splice(this.keys.indexOf(key), 1);
        this.keys.push(key);
        return val;
    }

    return -1;
};

put(key, value) {
    let obj = this.cache[key];

    // if key is already in the cache
    // remove key so we can add it on the end later
    if (obj !== undefined) {
        this.keys.splice(this.keys.indexOf(key), 1);
    }

    // if adding key is already over the capacity
    // we are going to remove the first item on the keys
    if (obj === undefined && this.keys.length === this.capacity) {
        const oldKey = this.keys.shift(); //?
        delete this.cache[oldKey]; //?
    }

    // add key to the keys, this is either an existing key or a new key
    this.keys.push(key); //?

    this.cache[key] = value;
}
Categories
Leetcode String

Reorder Log Files

let reorderLogFiles = function(logs) {

    let alpha = [],
        numbers = [];

    const isNumber = (str) => {
        const [, content] = str.split(' ');
        return content.match(/\d+/);
    }

    const getBody = (str) => {
        return str.substring(str.indexOf(' ') + 1);
    }

    // separate alpha from numbers
    logs.forEach(log => {
        if (isNumber(log)) {
            numbers.push(log);
        }
        else {
            alpha.push(log);
        }
    });

    let comparator = (x, y) => {
        let compareResult = getBody(x).localeCompare(getBody(y));
        if (compareResult === 0) {
           return x.localeCompare(y);
        }
        return compareResult;
    }

    return [...alpha.sort(comparator), ...numbers];
};
Categories
Breadth First Search Leetcode Recursion

Oranges Rotting

let orangesRotting = function(grid) {

    const FRESH = 1,
          ROTTEN = 2,
          VISITED = -1;
    let rotten = [],
        totalFresh = 0,
        totalEmpty = 0,
        total = 0;

    function getAdjacents(row, col) {
        let result = [];
        // check top
        if (row > 0 && grid[row -1][col] === FRESH) {
            grid[row -1][col] = VISITED;
            result.push([row - 1, col]);
        }

        // check bottom
        if (row < grid.length - 1 && grid[row + 1][col] === FRESH) {
            grid[row +1][col] = VISITED;
            result.push([row + 1, col]);
        }

        // check left;
        if (col > 0 && grid[row][col - 1] === FRESH) {
            grid[row][col - 1] = VISITED;
            result.push([row, col - 1]);
        }

        // check right
        if (col < grid[row].length - 1 && grid[row][col + 1] === FRESH) {
            grid[row][col + 1] = VISITED;
            result.push([row, col + 1]);
        }

        return result;
    }

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            const data = grid[i][j];
            if (data === ROTTEN) {
                rotten.push(...getAdjacents(i, j));
            }
            else if (data === FRESH || data === VISITED) {
                totalFresh++;
            }
            else {
                totalEmpty++;
            }
            total++;
        }
    }

    totalFresh -= rotten.length;
    let minute = 0;
    while (rotten.length) {
        let len = rotten.length;
        while (len --> 0) {
            let point = rotten.pop();
            let [row, col] = point;
            grid[row][col] = ROTTEN;
            rotten.unshift(...getAdjacents(row, col));
        }

        totalFresh -= rotten.length;
        minute++;
    }

    if (total === totalEmpty) return 0;

    let hasFreshOranges = totalFresh > 0;
    if (hasFreshOranges) return -1;

    return minute;
};
Categories
Leetcode Parenthesis Recursion String

Decode String

let decodeString = function(str) {

    if (str.indexOf("[") < 0) {
        return str;
    }

    let openingIndex = [];
    let newStr = "";
    for (let i = 0; i < str.length; i++) {
        if (str[i] === "[") {
            openingIndex.push(i);
            newStr += str[i];
        }
        else if (str[i] === "]") {
            let opening = openingIndex.pop();
            let allMultipliers = str.substring(0, opening).match(/\d+/g);
            let multiplier = allMultipliers[allMultipliers.length - 1];
            let data = str.substring(opening + 1, i);
            if (data.indexOf("[") < 0) {
                newStr = newStr.substring(0, newStr.lastIndexOf("[") - multiplier.length) + data.repeat(multiplier);
                console.log({opening, multiplier, data, newStr});
            }
            else {
                newStr += str[i];
            }
        }
        else {
            newStr += str[i];
        }
    }

    return decodeString(newStr);
};