मान लीजिए हमारे पास dictionary नामक शब्दों की एक लिस्ट है और हमारे पास start और end नामक दो अन्य स्ट्रिंग्स हैं। हम start से end तक एक बार में एक वर्ण बदलकर पहुंचना चाहते हैं और प्रत्येक परिणामी शब्द dictionary में भी होना चाहिए। शब्द केस-सेंसिटिव हैं। तो हमें end तक पहुंचने में लगने वाले न्यूनतम चरणों की संख्या ढूंढनी है। यदि संभव नहीं है तो -1 लौटाएं।
उदाहरण के लिए, यदि इनपुट dictionary = ["may", "ray", "rat"], start = "rat", end = "may" है, तो आउटपुट 3 होगा, क्योंकि हम यह पथ चुन सकते हैं: ["rat", "ray", "may"]।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम BFS (ब्रेडथ-फर्स्ट सर्च) का उपयोग करेंगे:
- dictionary := q में मौजूद सभी यूनिक तत्वों का सेट
- q := (start, 1) पेयर के साथ डबल-एंडेड क्यू
- जब तक q खाली नहीं है:
- (word, distance) := q का बायां तत्व, बायां तत्व हटाएं
- यदि word == end है, तो distance लौटाएं
- i को 0 से word की लंबाई - 1 तक लूप चलाएं:
- "abcdefghijklmnopqrstuvwxyz" के प्रत्येक वर्ण c के लिए:
- next_word := word[0:i] + c + word[i+1:]
- यदि next_word, dictionary में है:
- next_word को dictionary से हटाएं
- (next_word, distance + 1) को q के अंत में जोड़ें
- "abcdefghijklmnopqrstuvwxyz" के प्रत्येक वर्ण c के लिए:
- -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