Trie의 최단 경로

Question

데이터 구조 프로젝트의 경우 "cat"과 "dog"두 단어 사이의 최단 경로를 찾아야하지만 한 번에 한 글자 만 변경할 수 있습니다. 트라이를 구현하여, 그리고 최단 경로 검색을 구현할 수있을 것

고양이 수 없습니다 -.> 침대 -> 톱니가 -> 개

모든 단어가 같은 길이 될 것입니다 및 I 사전 파일에서 단어를 채우고 있습니다. 단어 사이를 이동해야합니다.

나는 tr을 사용하는 것이 실제로 불가능하다고 생각합니다. 즉, 누구라도 지식이 있습니까?

Answer 1

당신은 VP-Tree을 사용하려는 알고리즘이 여기에서 찾을 수 있습니다 Levenshtein distance AC 구현이라고는 코드는 답변으로 게시 너무 깁니다
C VP-Tree

Answer 2

이런 종류의 더 나은 데이터 구조 문제의 그래프입니다. 단어 사다리라고하며 여기에서 확인할 수 있습니다 : http://en.wikipedia.org/wiki/Word_ladder.

Answer 3

당신이 찾고있는 것은 간단한 BFS입니다. 사전 인에서 트라이의 종류에 짧은 과거의 당신은 일반적으로 구성하는 것이

words = {"cat", "dog", "dot", "cot"} 
mark = {0, 0, 0, 0} 
distance = {0, 0, 0, 0} 
queue Q 
start_word_index = 0; // words[0] -> "cat" 
destination_word_index = 1; // words[1] -> "dog" 
Q.push(start_word_index) 
while(Q is not empty) { 
    word_index = Q.pop() 
    for each `words[j]` { 
     if (difference between `words[word_index]` and `words[j]` is only 1 character) AND 
      (`mark[j]` is not 1) { 
      mark[j] = 1 
      Q.push(j) 
      distance[j] = distance[word_index] + 1 
     } 
    } 
} 

if mark[destination_word_index] is 0 { 
    print "Not reachable" 
} else { 
    print "Distance is ", distance[destination_word_index] 
}