Program to find number of steps required to change one word to another in Python

Suppose we have a list of words called dictionary and we have another two strings start and end. We want to reach from start to end by changing one character at a time and each resulting word should also be in the dictionary. Words are case-sensitive. So we have to find the minimum number of steps it would take to reach at the end. If it is not possible then return -1.

So, if the input is like dictionary = ["may", "ray", "rat"] start = "rat" end = "may", then the output will be 3, as we can select this path: ["rat", "ray", "may"].

To solve this, we will follow these steps −

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

Example (Python)

Let us see the following implementation to get better understanding −

 Live Demo

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))

Input

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

Output

3