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

ধরুন আমাদের কাছে A থেকে Z অক্ষর সম্বলিত একটি বার্তা রয়েছে যা নিম্নলিখিত ম্যাপিং ব্যবহার করে সংখ্যাগুলিতে এনকোড করা হচ্ছে − 'A' → 1, 'B' → 2 ... 'Z' → 26. তাই যদি আমাদের একটি অ-খালি স্ট্রিং থাকে, যেখানে শুধুমাত্র সংখ্যা থাকে, তাহলে আমাদের খুঁজে বের করতে হবে, কত উপায়ে ডিকোড করা যেতে পারে। সুতরাং যদি স্ট্রিংটি "12" এর মতো হয়, তবে এটি "AB" বা "L" থেকে তৈরি করা যেতে পারে, তাই দুটি সম্ভাব্য উপায় রয়েছে। সুতরাং উত্তর হবে 2.

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• আমরা ডাইনামিক প্রোগ্রামিং ব্যবহার করে এর সমাধান করব।
• n :=s এর দৈর্ঘ্য
• dp :=0s এর n সংখ্যা সহ একটি অ্যারে
• যদি s[0] '0' না হয়, তাহলে dp[0] :=1
• আমি 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 দ্বারা বাড়ান
• ডিপির শেষ উপাদান ফেরত দিন

উদাহরণ(পাইথন)

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

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