home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

Decode Ways ใน Python - จำนวนวิธีถอดรหัสข้อความ

สมมติว่าเรามีข้อความที่มีตัวอักษร A ถึง Z ถูกเข้ารหัสเป็นตัวเลขด้วย mapping: 'A' → 1, 'B' → 2 ... 'Z' → 26 ถ้าเรามีสตริงไม่ว่างที่ประกอบด้วยตัวเลขเท่านั้น เราต้องหาว่าสามารถถอดรหัสได้กี่วิธี ตัวอย่าง สตริง "12" สามารถสร้างจาก "AB" (1, 2) หรือ "L" (12) ดังนั้นมี 2 วิธี

ขั้นตอนการทำงาน (Dynamic Programming)

  1. แก้ด้วย Dynamic Programming
  2. n := length of s
  3. dp := array ขนาด n เติม 0
  4. ถ้า s[0] != '0' ให้ dp[0] := 1
  5. วนลูป i จาก 1 ถึง n-1:
    • x := s[i] as integer, y := substring s[i-1:i+1] as integer
    • ถ้า 1 ≤ x ≤ 9 ให้ dp[i] := dp[i] + dp[i-1]
    • ถ้า 10 ≤ y ≤ 26:
      • ถ้า i-2 ≥ 0 ให้ dp[i] := dp[i] + dp[i-2] มิฉะนั้นเพิ่ม dp[i] 1
  6. คืนค่าองค์ประกอบสุดท้ายของ dp

ตัวอย่างโค้ด (Python)

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 1 <= x <= 9:
                dp[i] += dp[i-1]
            if 10 <= 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