حلولي في كودرهب

عدد طرق فك التشفير

متوسط10 نقاطPython

الوصف

يتم تشفير رسالة سرية كسلسلة من الأرقام، ويمكن فك تشفيرها باستخدام خريطة معينة حيث:

"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) في الذاكرة.

في هذه الصفحة