Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में एक शब्द को दूसरे शब्द में बदलने के लिए आवश्यक चरणों की संख्या खोजने का प्रोग्राम


मान लीजिए हमारे पास 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 के अंत में जोड़ें
  • -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
  1. 8-पज़ल को हल करने के चरणों की संख्या ज्ञात करने का पायथन प्रोग्राम 8-पज़ल को हल करने के चरणों की संख्या ज्ञात करने का पायथन प्रोग्राम

    मान लीजिए हमारे पास एक 3x3 बोर्ड है जहां सभी संख्याएं 0 से 8 की रेंज में हैं और कोई दोहराव नहीं है। अब हम 0 को उसके 4 पड़ोसियों में से किसी एक के साथ स्वैप कर सकते हैं, और हम इसे हल करके सभी व्यवस्थित क्रम प्राप्त करने की कोशिश कर रहे हैं, हमें लक्ष्य तक पहुंचने के लिए आवश्यक न्यूनतम चरणों की संख्य

  1. - पायथन में एक स्ट्रिंग को दूसरी स्ट्रिंग का सबस्ट्रिंग बनाने के लिए आवश्यक न्यूनतम संक्रियाओं की संख्या खोजने का प्रोग्राम

    मान लीजिए हमारे पास दो स्ट्रिंग्स s और t हैं, हमें s के लिए आवश्यक न्यूनतम संक्रियाओं की मात्रा ढूंढनी है ताकि t, s का सबस्ट्रिंग बन जाए। अब, प्रत्येक संक्रिया में, हम s में किसी भी स्थिति को चुन सकते हैं और उस स्थिति के वर्ण को किसी अन्य वर्ण में बदल सकते हैं। उदाहरण के लिए, यदि इनपुट है s = abbpq

  1. - पायथन प्रोग्राम: लिस्ट में सबसे बड़ी संख्या ढूंढें

    इस लेख में, हम दिए गए प्रॉब्लम स्टेटमेंट को हल करने के समाधान और दृष्टिकोण के बारे में सीखेंगे। प्रॉब्लम स्टेटमेंट लिस्ट इनपुट दिए जाने पर, हमें दी गई लिस्ट में सबसे बड़ी संख्या ढूंढने की आवश्यकता है। यहां हम दो दृष्टिकोणों पर चर्चा करेंगे: सॉर्टिंग तकनीकों का उपयोग करना बिल्ट-इन max() फंक्शन का