Wildcard Bucket 인덱싱으로 $O(N^2)$ 전처리를 $O(N \cdot L)$로 최적화

Context

단어 간 Hamming distance 기반의 Graph Traversal 구현 시 발생하는 비효율적 전처리 구조 분석. 전체 사전의 모든 단어를 전수 비교하는 Naive approach로 인한 $O(N^2 \cdot L)$ 시간 복잡도의 한계점 노출.

Technical Solution

• Wildcard Bucket Index 도입을 통한 인접 노드 탐색 최적화
• 단어의 각 자리를 와일드카드로 치환한 Pattern Key 기반 Hash Map 설계
• $O(L)$ 시간 복잡도로 Neighbor를 추출하는 효율적 인덱싱 구조 채택
• Unweighted Graph 특성을 고려하여 Dijkstra 대신 단순 BFS를 통한 최단 경로 탐색
• Start와 Target 양방향에서 동시 탐색하는 Bidirectional BFS 적용으로 Search Space 축소
• 메모리 효율성을 위해 명시적 Adjacency List 대신 인덱스 기반 런타임 생성 방식 활용