สมมติว่าเรามีข้อความที่มีตัวอักษรจาก A ถึง Z ถูกเข้ารหัสเป็นตัวเลขโดยใช้การจับคู่ต่อไปนี้ - 'A' → 1, 'B' → 2 ... 'Z' → 26. ดังนั้นถ้าเรามีสตริงที่ไม่ว่างหนึ่งสตริงที่มีตัวเลขเท่านั้น เราก็ต้องหาว่าจะสามารถถอดรหัสได้กี่วิธี ดังนั้นถ้าสตริงเป็นเหมือน "12" ก็สามารถสร้างจาก "AB" หรือ "L" ได้ดังนั้นจึงมีสองวิธีที่เป็นไปได้ ดังนั้นคำตอบจะเป็น 2.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เราจะแก้ปัญหานี้โดยใช้โปรแกรมไดนามิก
- n :=ความยาวของ s
- dp :=อาร์เรย์ที่มี n จำนวน 0s
- ถ้า s[0] ไม่ใช่ '0' ดังนั้น dp[0] :=1
- สำหรับฉันอยู่ในช่วง 1 ถึง n – 1
- x :=s[i] เป็นจำนวนเต็ม y :=สตริงย่อยของ s จากดัชนี i – 1 ถึง i + 1 เป็นจำนวนเต็ม
- ถ้า 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
ตัวอย่าง(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 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
