CollegeStash

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
const coinChange = (coins, amount) => {
  if (!coins) {
    return -1;
  }
  return getCoinChangeMin(coins, amount, {});
};

const getCoinChangeMin = (coins, amount, dp) => {
  if (amount < 0) {
    return -1;
  }
  if (amount === 0) {
    return 0;
  }
  if (amount in dp) {
    return dp[amount];
  }
  let min = Number.MAX_VALUE;
  for (const coin of coins) {
    let currMin = getCoinChangeMin(coins, amount - coin, dp);
    if (currMin >= 0 && currMin < min) {
      min = currMin;
    }
  }
  return dp[amount] = min === Number.MAX_VALUE ? -1 : min + 1;
};

class TrieNode {
  constructor(val = null) {
    this.val = val;
    this.children = {};
    this.isWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(str) {
    let current = this.root;
    for (const char of str.split('')) {
      if (!(char in current.children)) {
        current.children[char] = new TrieNode(char);
      }
      current = current.children[char];
    }
    current.isWord = true;
  }

  search(str) {
    let current = this.root;
    for (const char of str.split('')) {
      if (char in current.children) {
        current = current.children[char];
      } else {
        return false;
      }
    }
    return current.isWord;
  }
}

const trie = new Trie();
trie.insert('john');
trie.insert('smith');
console.log(trie.search('john'));  // true
console.log(trie.search('smith')); // true
console.log(trie.search('johny')); // false
console.log(trie.search('Tesla')); // false
console.log(trie.search('John'));  // false

Demo

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  if  (!digits) {
    return [];
  }
const result = [];
const map = {2: 'abc',
3: 'def',
4:'ghi',
5:'jkl',
6:'mno',
7:'pqrs',
8: 'tuv',
9:'wxyz',};
  computeCombinations(map, digits, 0, result, '');
  return result;
};

const computeCombinations = (map, digits, index, result, str) => {
  if (index === digits.length) {
    result.push(str);
  } else {
    for (const letter of map[digits[index]].split('')) {
       computeCombinations(map, digits, index + 1, result, str + letter);
    }
  }
};

/**
* @param {string[]} words
* @param {number} k
* @return {string[]}
*/
const topKFrequent = (words, k) => {
  const wordFreq = {};
  for (const word of words) {
    if (word in wordFreq) {
      wordFreq[word]++;
    } else {
      wordFreq[word] = 0;
    }
  }

  return [...new Set(words)].sort((a, b) => {
    if (wordFreq[a] === wordFreq[b]) {
      return a.localeCompare(b);
    } else {
      return wordFreq[b] - wordFreq[a];
    }
  }).slice(0, k);
};

// Knuth–Morris–Pratt algorithm.
const patternMatch = function(pattern, str) {
  let i = 0;
  let j = 0;
  let n = str.length;
  let m = pattern.length;
  const lps = [];

  // Compute longest prefix string.
  computeLPS(pattern, m, lps);

  while (i < n) {
    if (str.charAt(i) === pattern.charAt(j)) {
      i++;
      j++;
    }
    if (j === m) {
      console.log('String found at: ' + (i - j));
      j = lps[j - 1];
    } else if (i < n && str.charAt(i) !== pattern.charAt(j)) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }
};

const computeLPS = function(pattern, m, lps) {
  let i = 1;
  let len = 0;
  while (i < m) {
    if (pattern.charAt(i) === pattern.charAt(len)) {
      lps[i++] = ++len;
    } else {
      if (len > 0) {
        len = lps[len - 1];
      } else {
        lps[i++] = 0;
      }
    }
  }
};

patternMatch('john', 'helloworldjohnhelloworldjohnn');
/*
"String found at: 10"
"String found at: 24"
*/

Demo

Find the longest common prefix for a list of strings.

const longestCommonPrefix = (arr) => {
  if (!arr || !arr.length) {
    return;
  }

  let low = 0;
  let high = arr[0].length - 1;

  for (const str of arr) {
    high = Math.min(str.length - 1, high);
  }

  let str = '';

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (hasPrefix(arr, low, mid)) {
      str += arr[0].substring(low, mid + 1);
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return str;
};

const hasPrefix = (arr, low, mid) => {
  const prefix = arr[0].substring(low, mid + 1);

  for (const str of arr) {
    if (!str.substring(low, mid + 1).startsWith(prefix)) {
      return false;
    }
  }

  return true;
};

console.log(longestCommonPrefix(['johnSmith', 'johnWick', 'john1'])); // 'john'
console.log(longestCommonPrefix(['jo1hnSmith', 'johnWick', 'john1'])); // 'jo'
console.log(longestCommonPrefix(['Smith', 'Wick', 'red'])); // ''

Demo

Runtime complexity: m*log(n)

m = length of the smallest string in the list.

n = length of the list.

Array.prototype.reduce = function(fn, initialValue) {
  let acc = initialValue;

  for (const [key, val] of Object.entries(this)) {
    if (acc === undefined && key === '0') {
      acc = this[0];
    } else {
      acc = fn.call(null, acc, this[key], key, this);
    }
  }
  return acc;
};

const arr = [3, 4, 5, 0, -1];

console.log(arr.reduce((acc, curr) => acc + curr)); // 11

Demo

Array.prototype.filter = function(callback, context) {
  const ret = [];
  for (const [key, val] of Object.entries(this)) {
    if (callback.call(context, this[key], key, this)) {
      ret.push(val);
    }
  }
  return ret;
};

console.log([4, -1, 1, 2, 3].filter(x => x >= 2)); // [4, 2, 3];

Demo