/**
 * @param {string[]} dictionary
 * @param {string} sentence
 * @return {string}
 */
 var replaceWords = function(dictionary, sentence) {
  const root = {
      val: '_',
      childs: {},
      word: '',
      valid: false
  };
  for(let d of dictionary) {
      let curr = root;
      for(let i = 0;i < d.length; i++) {
          if(curr.childs[d[i]]) {
              curr = curr.childs[d[i]];
          } else {
              let node = {
                  val: d[i],
                  childs:[],
                  word: curr.word + d[i],
                  valid: false
              }
              curr.childs[d[i]] = node;
              curr = node;
          }
      }
      curr.valid = true;
  }
  return sentence.split(' ').map(e => {
      let curr = root;
      for(let i = 0; i < e.length; i++) {
          if(curr.childs[e[i]]) {
              curr = curr.childs[e[i]];
              if(curr.valid) {
                  return curr.word;
              }
          } else {
              return e;
          }
      }
      return e;
  }).join(' ')
};