Leetcode: Replace Words

replace_words.js

function TrieNode(char, terminal = false) {
  this.char = char;
  this.terminal = terminal;
  this.nextChars = {};
}

function Trie() {
  this.root = new TrieNode(null);
}

Trie.prototype.insertWord = function (word) {
  let node = this.root;

  [...word].forEach((char) => {
    if (!node.nextChars[char]) {
      node.nextChars[char] = new TrieNode(char);
    }
    node = node.nextChars[char];
  });
  node.terminal = true;
};

Trie.prototype.hasPrefix = function (word) {
  let node = this.root;

  for (let i = 0; i < word.length; i++) {
    let char = word[i];
    if (!node.nextChars[char]) {
      return [false, node];
    }
    node = node.nextChars[char];
  }
  return [true, node];
};

Trie.prototype.hasWord = function (word) {
  let [found, { terminal }] = this.hasPrefix(word);
  return found && terminal;
};

Trie.prototype.getShortestPrefixWord = function (word) {
  let node = this.root;
  let prefixWord = [];

  for (let i = 0; i < word.length; i++) {
    let char = word[i];

    if (!node.nextChars[char]) {
      break;
    }
    prefixWord.push(char);
    node = node.nextChars[char];
  }

  if (node.terminal) {
    return prefixWord.join("");
  }
  return "";
};

function replaceWords(dict, sentence) {
  let trie = new Trie();

  dict.forEach((word) => trie.insertWord(word));

  return sentence
    .split(" ")
    .map((word) => {
      let prefix = trie.getShortestPrefixWord(word);

      if (prefix === "") {
        return word;
      }
      return prefix;
    })
    .join(" ");
}

console.log(
  replaceWords(
    ["cat", "ca", "bat", "rat"],
    "the cattle was rattled by the battery"
  )
); // the cat was rat by the bat