โปรแกรมหาจำนวนขั้นตอนเปลี่ยนคำหนึ่งเป็นอีกคำหนึ่งใน Python

สมมติว่าเรามีพจนานุกรมคำ dictionary และสตริง start และ end ต้องการไปจาก start ถึง end โดยเปลี่ยนตัวอักษรทีละตัว และคำทุกขั้นตอนต้องอยู่ในพจนานุกรม คำคำนึงถึงพิมพ์เล็ก/ใหญ่ หาจำนวนขั้นตอนขั้นต่ำ ถ้าไม่ได้คืน -1

เช่น dictionary = ["may", "ray", "rat"] start = "rat" end = "may" ผลลัพธ์ = 3 เส้นทาง: ["rat", "ray", "may"]

ขั้นตอนการแก้ปัญหา (BFS)

• dictionary := set(dictionary)
• q := deque([(start, 1)])
• while q ไม่ว่าง:
  • (word, distance) := q.popleft()
  • ถ้า word == end คืน distance
  • วน i = 0..len(word)-1:
    • วนทุกตัวอักษร c ใน 'abcdefghijklmnopqrstuvwxyz':
      • next_word := word[:i] + c + word[i+1:]
      • ถ้า next_word in dictionary: ลบออกจาก dictionary, push (next_word, distance+1) เข้า queue
• คืน -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