Permutation 제거 및 Canonical Mapping 기반 $O(L \log L)$ 검색 최적화

Context

입력 문자열의 모든 조합을 생성하는 Naive approach의 지수적 시간 복잡도로 인한 성능 한계 발생. 10글자 단어 기준 3,628,800개의 Permutation 생성이 필요하여 실시간 서비스 적용 불가능한 구조 분석.

Technical Solution

• 알파벳 정렬을 통한 Canonical Sorted-Key 생성으로 Anagram 간 동일 키를 부여하는 정규화 전략 채택
• 정규화된 키를 Hash Map의 Key로, 매칭 단어 리스트를 Value로 저장하여 Lookup 시간 복잡도를 $O(1)$로 단축
• Subset 검색 및 Wildcard 대응을 위해 문자 단위 노드로 구성된 Trie 구조를 통한 탐색 공간 Pruning 구현
• 메모리 제약 환경 대응을 위해 26개 알파벳 빈도수를 Vector로 표현하고 Vector Subtraction으로 포함 관계를 판별하는 Bit-Vector 최적화 적용
• 메모리 효율 극대화를 위해 접미사가 중복되는 노드를 병합하는 DAWG(Directed Acyclic Word Graph) 구조 검토