Chương trình tìm số bước tối thiểu biến đổi từ từ này sang từ kia trong Python

Cho từ điển dictionary, từ bắt đầu start và từ kết thúc end. Mỗi bước thay đổi đúng 1 ký tự, từ mới phải có trong từ điển. Tìm số bước tối thiểu từ start đến end. Không thể thì trả về -1.

Ví dụ: dictionary=["may","ray","rat"], start="rat", end="may" → đường đi: rat → ray → may (3 bước).

Giải thuật (BFS trên đồ thị từ)

• Chuyển từ điển thành tập hợp set để tra O(1).
• Hàng đợi BFS lưu (word, distance).
• Pop từ hàng đợi, nếu trùng end → trả về distance.
• Sinh tất cả từ lân cận bằng cách thay mỗi vị trí bằng 'a'..'z', nếu có trong từ điển → push vào hàng đợi và xóa khỏi từ điển (đánh dấu đã thăm).
• Hết hàng đợi → trả về -1.

Mã nguồn Python

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))  # Output: 3

Đầu vào

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

Đầu ra

3