내 질문은 (는) Algorithm to transform one word to another through valid words다양한 사전으로 거리 편집
과 비슷하지만 큰 차이가 있습니다. 나는 하나의 고정 된 단어 "제임스"와 다양한 사전을 i/p라고합니다. 물론 사전을 사전 처리 할 수는 없습니다.
그래서 "JAMES"를 "JOHNY"로 처리하기위한 최소 비용을 다른 사전을 입력으로 찾아야합니다.
"JAMES"라는 단어를 사전 처리하여 런타임시 편집 거리 계산의 최소 횟수를 수행해야합니까? 너희들은 뭐라고 제안하니?
먼저 규칙을 올바르게 정의해야합니다. 여러 문자를 추가하거나 삭제하고 한 문자를 대체하는 등의 "편집"이 가능합니까?
어쨌든 - 저는 분명히 시작합니다 - 각 단어가 직접 편집 할 수있는 모든 단어로 연결되는 그래프를 만듭니다. 그런 다음 순환을 피하기 위해 방문한 요소를 "더티 (dirty)"로 표시 한 다음 심도 한도의 재귀를 사용하여 솔루션을 찾거나 모든 경로가 그 깊이에 더러워지기 전까지 한 편집 솔루션, 두 편집 솔루션 등이 있는지 확인하십시오. ("더티 (dirty)"멤버에서 시도한 심도를 기록하면 심도 한계를 증가시킬 때마다 클리닝에 대해 걱정할 필요가 없습니다. 더러운 서브 트리를 다시 표시하지 않도록 지정할 수도 있습니다 .)
나는 규칙이 당신이 인용 한 질문과 유사하다고 가정하고있다. 즉 한 번에 하나의 편집 만 허용되며 각 중간 단어는 주어진 사전에 있어야한다.
같이 Recurse 및 모든 고유 단어에 대한 노드를 만들어 유지한다. 노드가 이미 생성 된 경우 가장자리 만 생성하면됩니다. 이것으로 전처리가 완료됩니다.
이제 사전이 주어지면 사전의 모든 첫 번째 단어를 찾습니다. 모든 성냥을 위해, 당신이 목적지 낱말을 도달 할 때까지, 두번째 수준 낱말을 더 발견하십시오.