পাইথনে ডিকোড ওয়েজ

मान लीजिए हमारे पास A से Z तक के अक्षरों वाला एक संदेश है जिसे निम्नलिखित मैपिंग का उपयोग करके संख्याओं में एन्कोड किया जा रहा है − 'A' → 1, 'B' → 2 ... 'Z' → 26। इसलिए यदि हमारे पास एक गैर-खाली स्ट्रिंग है, जिसमें केवल अंक हैं, तो हमें यह ढूंढना होगा कि इसे कितने तरीकों से डिकोड किया जा सकता है। इसलिए यदि स्ट्रिंग "12" की तरह है, तो इसे "AB" या "L" से बनाया जा सकता है, इसलिए दो संभावित तरीके हैं। तो उत्तर 2 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −

• हम इसे डायनामिक प्रोग्रामिंग का उपयोग करके हल करेंगे।
• n := s की लंबाई
• dp := n संख्या के 0s के साथ एक सरणी
• यदि s[0] '0' नहीं है, तो dp[0] := 1
• i के लिए 1 से n - 1 तक रेंज में
  • x := s[i] पूर्णांक के रूप में, y := इंडेक्स i - 1 से i + 1 तक s का सबस्ट्रिंग पूर्णांक के रूप में
  • यदि x >= 1 और y <= 9, तो dp[i] := dp[i] + dp[i - 1]
  • यदि y >= 10 और y <= 26
    • यदि i - 2 >= 0, तो dp[i] := dp[i] + dp[i - 2], अन्यथा dp[i] को 1 से बढ़ाएं
• dp का अंतिम तत्व लौटाएं

उदाहरण (पाइथन)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −

class Solution(object):    def numDecodings(self, s):       n = len(s)       dp = [0 for i in range(n)]       if s[0]!='0':          dp[0]=1       for i in range(1,n):          x = int(s[i])          y = int(s[i-1:i+1])          if x>=1 and x<=9:             dp[i]+=dp[i-1]          if y>=10 and y<=26:             if i-2>=0:                dp[i]+=dp[i-2]             else:                dp[i]+=1       return dp[-1] ob1 = Solution() print(ob1.numDecodings("226"))

इनपुट

"226"

आउटपुट

3