Trie

Trie 자료 구조를 활용한 문제 모음

• HashMap(dict in python)을 활용해서 만든 트리
  • 여러 단어들을 하나의 트리에 넣어서, prefix/whole word 처리를 할 때 유용하다. * Trie 구조 생성 복잡도 O(L*N)(L: 문자열 최대 길이, N: 문자열 총 개수)
    • 관련 문제들 (어려운 문제가 아닌 경우, Trie 를 따로 만들지 않고 set 또는 dict으로 풀린다))
      • 전화번호 목록, 개미굴
      • 가사 검색
        • 패턴 매칭 시, Trie 활용 팁 두가지
          1. 각 Trie node에 length 변수 추가 후 Trie 구축중에 계산 (length: 해당 노드 이후 매칭되는 단어의 총 개수)
          2. prefix 단어(e.g. ???ord) matching 에는 단어를 거꾸로 해서 넣은 Trie 사용, postfix 단어(e.g. ord???) matching 에는 일반 Trie 사용
          3. 만약 매칭해야되는 단어의 길이가 다양할 경우, 길이에 따른 여러개의 Trie를 구성하는 것이 좋다.
      • 휴대폰 자판
        • Trie에 포함된 전체 단어들에 대해서 한꺼번에 재귀로 계산할 수 있는가? (풀긴 풀었는데 코드를 다시 한번 생각)