عدد طرق فك التشفير
الوصف
يتم تشفير رسالة سرية كسلسلة من الأرقام، ويمكن فك تشفيرها باستخدام خريطة معينة حيث:
"1" → 'A'
"2" → 'B'
"26" → 'Z'
المطلوب هو كتابة دالة تقوم بحساب عدد الطرق الممكنة لفك التشفير. إذا كانت الرسالة تحتوي على أرقام لا يمكن فك تشفيرها (مثل الرقم 0 إذا لم يكن جزءًا من رمز مزدوج صالح مثل "10" أو "20")، فإن فك التشفير يصبح غير ممكن.
المتطلبات:
يجب فك التشفير بناءً على الخريطة المذكورة.
يتم فك التشفير بطريقتين:
رمز فردي (مثل "1" → "A").
رمز مزدوج (مثل "12" → "L").
إذا كانت الرسالة تحتوي على سلسلة أرقام غير قابلة للفك، يجب إرجاع 0.
مثال :
المدخل : s = "226"
المخرج : 3
الشرح:
يمكن فك التشفير بـ 3 طرق:
"2" → "B", "2" → "B", "6" → "F" → "BBF".
"22" → "V", "6" → "F" → "VF".
"2" → "B", "26" → "Z" → "BZ".
حالات خاصة:
إذا كانت السلسلة تبدأ بـ '0':
المدخل: "06"
المخرج: 0 (لا يمكن فك التشفير).
إذا كانت السلسلة فارغة:
المدخل: ""
المخرج: 0 (لا توجد طرق لفك التشفير).
الهدف:
معالجة النصوص المشفرة وإيجاد عدد الطرق الممكنة لفك التشفير.
التعامل مع الحواف الخاصة مثل الأرقام غير الصالحة ودمج الرموز الفردية والمزدوجة.
أمثلة
| المدخلات | المخرجات المتوقعة |
|---|---|
s = "1" | 1 |
s = "12" | 2 |
s = "06" | 0 |
s = "" | 0 |
الحل
from typing import List
def num_decodings(s: str) -> int:
if not s:
return 0
prev, cur = 1, 1 if s[0] != "0" else 0
for i in range(1, len(s)):
nxt = cur if s[i] != "0" else 0
if 10 <= int(s[i - 1:i + 1]) <= 26:
nxt += prev
prev, cur = cur, nxt
return curملاحظات
برمجة ديناميكية (DP) بمتغيرين فقط: عدد الطرق حتى الحرف السابق، وحتى الحرف الذي قبله.
لكل رقم جديد:
- إذا لم يكن
0، يصلح وحده، فنضيف طرق الموضع السابق. - إذا كان الرقمان الأخيران بين
10و26، يصلحان معًا، فنضيف طرق الموضع الذي قبله.
السلسلة الفارغة أو التي تبدأ بـ 0 نتيجتها 0. مثال: "226" له 3 طرق.
التعقيد: O(n) في الوقت، وO(1) في الذاكرة.