[JS Algorithm] 자동완성 (Trie 구조)

1. Trie

• 문자열의 구조를 저장할 때 주로 사용하는 자료구조로 해당 문자열 다음에 어떤 문자가 오는지 파악할 수 있음

2. 구현 과정

1. 트라이 구조 만들기

function makeTrie(words) {
  const root = {};
  
  for (let word of words) {
    let current = root;
    
    for (const letter of word) {
      if (!current[letter]) {
        current[letter] = [0, {}]; 
        // [count, 뒤애 올 단어를 저장하는 dict] 배열을 갖는 자료구조를 만들어줌! 
      }
      
      // letter가 다시 등장한 경우!
      current[letter][0] = 1 + (current[letter][0] || 0);
      current = current[letter][1];
      // 이 때, letter 노드 아래에 자식 노드가 있는 경우에는 거기에 count + 1 되어서
      // 저장이 되고, 그게 아닌 경우에는 [count, 저삭 노드 dict] 구조가 새로 생성되어 배정된다.
    }
  }
  
  return root;
}

2. Solution

function solution(words) {
  let ans = 0;
  const trie = makeTrie(words);
  
  for (const word of words) {
    let count = 0; // 각 워드마다 필요한 count의 개수
    let current = trie; // 루트부터 시작!
    
    for (const [index, letter] if [...word].entries()) {
      count += 1;
      
      if (current[letter] <= 1) {
        break;
      }
      
      current = current[letter][1];
    }
    
    ans += count;
  }
  
  return ans;
}