자료구조 Trie

Trie 자료구조란 입력받은 문자열들을 트리형태로 저장하는 자료구조입니다.

주로 문자열 탐색이나 자동 완성 기능 등에 자주 사용됩니다.

 

["abc", "ab", "bc", "b", "cd"] 를 Trie자료구조로 표현해보면, 

이러한 구조를 가지므로, a를 검색했을때 하위요소인 b를 자동완성기능으로 보여주고, ab를 검색했을때, 하위요소 c와 d를 추가해서 보여줄 수 있습니다.

 

Trie자료구조를 이용하는 leetcode 문제를 소개해드리겠습니다.

 

14. Longest Common Prefix

문자열 배열 중에서 가장 긴 공통 접두사 문자열을 찾는 함수를 작성하세요.

공통적인 접두사가 없으면 빈 문자열을 반환합니다.

입력: strs = ["flower","flow","flight"]
출력: "fl"

입력: strs = ["dog","racecar","car"]
출력: ""
설명: 입력 문자열 사이에 공통된 접두사가 없습니다.

 

head로 부터 하위요소가 1개가 아니라면, 공통된 접두사가 아닙니다.

하위요소가 1개가 아닐때까지, 문자열을 더해가면 될 것 같습니다.

해당 방식을 위해서는 단어가 끝났는지 확인해줘야합니다.

그렇지않으면 , input =["ab","a"] 일때, a의 children이 "b" 1개 이므로, "ab"가 출력이 될 것입니다.

 

trie자료구조를 만들기 위해 class를 하나 만들어줍니다.

 

코드로 구현한다면, 노드를 생성하고, 노드를 찾고, 노드를 추가해주는 함수가 필요할 것입니다.

class Trie {

  constructor() {

    this.root = this.createNode("");

  }

  //node를 생성합니다.

  createNode(word) {

    return { value: word, children: [], isEnd: false };

  }

  //현재 node와 문자를 받아와 해당 문자가 존재하는지 탐색합니다.

  findNode(word, node) {

    return node.children.find((v) => v.value === word) || null;

  }

  //문자열을 받아와 한글자씩 node를 탐색합니다.

  insert(str) {

    let current = this.root;

    for (const word of str) {

      let child = this.findNode(word, current); //현재 node에서 해당 문자가 존재하는지 탐색 후 저장

      if (!child) {

        child = this.createNode(word);

        current.children.push(child); //현재 node에서 해당 문자가 없다면, 노드생성 후 저장

      }

      current = child; //다음 node로 넘어감.

    }

    current.isEnd = true; //마지막 노드에서 단어의 끝맺음을 저장.

  }

}

 

입력받은 배열의 문자열을 순회하면서,  insert 를 해줍니다.

후, root의 children의 갯수가 1이 아닐때까지 탐색합니다.

 

var longestCommonPrefix = function (strs) {

  let list = new Trie();

  let result = "";

  for (const str of strs) { //배열을 순회하며 문자열을 insert.

    if (str === "") return "";

    list.insert(str);

  }

  let node = list.root; // Trie의 root node 부터 시작합니다.

  while (node.children.length === 1) { // children의 갯수가 1이라면 계속 반복.

    const child = node.children[0];

    result += child.value;

    if (child.isEnd) return result; //해당 node에서 끝나는 단어가 있다면 종료.

    node = child; //다음 node로 이동

  }

  return result;

};