자동완성

https://school.programmers.co.kr/learn/courses/30/lessons/17685

프로그래머스

입력받는 키워드 ( char ) 를 tree 로 만들고,

각 키워드를 순회하며 중복되지 않은 ( 겹치는 단어가 없는 ) node 에 도달하면 해당 node 의 depth 가 단어를 검색하는데 필요한 최소 단어 갯수이다.

 

tree 를 만드는 전체 과정은 O(N*2) 이 수행되고, 단어를 찾는 과정은 O(N) 이 수행된다.

function solution(words) {
  var rootDict = new Map();

  function update(word) {
    var curDict = rootDict;
    for (var idx = 0; idx < word.length; idx++) {
      var char = word[idx];
      if (!curDict.has(char)) {
        var tmpDict = new Map();
        // set item
        curDict.set(char, { dict: tmpDict, count: 0 });
      }
      
      var item = curDict.get(char);
      
      item.count += 1;
      curDict = item.dict;
    }
  }

  function count(word) {
    var curDict = rootDict;
    for (var idx = 0; idx < word.length; idx++) {
      var char = word[idx];
      var item = curDict.get(char);
      if (item.count == 1) return idx + 1;

      curDict = item.dict;
    }
    return idx;
  }

  words.forEach((word) => update(word));
  var answer = words.reduce(
    (accumulator, currentValue) => accumulator + count(currentValue),
    0
  );
  return answer;
}