Python에서 한 단어를 다른 단어로 변경하는 데 필요한 단계 수를 찾는 프로그램

사전이라는 단어 목록이 있고 또 다른 두 개의 문자열 시작과 끝이 있다고 가정합니다. 우리는 한 번에 한 문자를 변경하여 처음부터 끝까지 도달하기를 원하며 각 결과 단어도 사전에 있어야 합니다. 단어는 대소문자를 구분합니다. 따라서 우리는 마지막에 도달하는 데 필요한 최소 단계 수를 찾아야 합니다. 가능하지 않으면 -1을 반환합니다.

따라서 입력이 사전 =["may", "ray", "rat"] start ="rat" end ="may"와 같으면 다음 경로를 선택할 수 있으므로 출력은 3이 됩니다. ["rat ", "레이", "할 수 있습니다"].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

dictionary := a new set with all unique elements present in
q = a double ended queue with a pair (start, 1)
while q is not empty, do
   (word, distance) := left element of q, and delete the left element
   if word is same as end, then
      return distance
      for i in range 0 to size of word - 1, do
         for each character c in "abcdefghijklmnopqrstuvwxyz", do
            next_word := word[from index 0 to i - 1] concatenate c concatenate word[from index (i + 1) to end]
            if next_word is in dictionary, then
               delete next_word from dictionary
               insert (next_word, distance + 1) at the end of q
return -1

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

from collections import deque
class Solution:
   def solve(self, dictionary, start, end):
      dictionary = set(dictionary)
      q = deque([(start, 1)])
      while q:
         word, distance = q.popleft()
         if word == end:
            return distance
         for i in range(len(word)):
            for c in "abcdefghijklmnopqrstuvwxyz":
               next_word = word[:i] + c + word[i + 1 :]
               if next_word in dictionary:
                  dictionary.remove(next_word)
                  q.append((next_word, distance + 1))
      return -1
ob = Solution()
dictionary = ["may", "ray", "rat"]
start = "rat"
end = "may"
print(ob.solve(dictionary, start, end))

입력

["may", "ray", "rat"], "rat", "may"

출력

3