Decode Ways

Q: كيف تتعامل مع الأصفار في Decode Ways؟

لا يكون 0 حرفًا بمفرده أبدًا، لذا يجب أن يقترن بالرقم الذي قبله مثل 10 أو 20 . وهو يضيف العدد من خانتين إلى الوراء فقط بعد 1 أو 2، ولا يفعل ذلك في غير هذه الحالة. ويعطي 0 في البداية، أو صفران متتاليان، أو 0 بعد رقم من 3 إلى 9.

متوسطالبرمجة الديناميكية

+10

رُمِّزت رسالة مكوّنة من أحرف كبيرة باستخدام A = 1 وB = 2، وهكذا حتى Z = 26، وكُتبت الرموز من دون فواصل. عند إعطائك سلسلة الأرقام s، أعد عدد الرسائل التي يمكن أن تكون قد أنتجتها.

يُقرأ الحرف من رقم واحد أو رقمين متجاورين، ولا يبدأ أي رمز بـ0: فـ06 لا يساوي 6، والصفر المنفرد ليس حرفًا. إذا لم تنجح أي قراءة، فأعد 0.

الدالة

numDecodings(s: string) → integer

sstring: سلسلة الأرقام المطلوب فك ترميزها
تُرجعinteger: عدد الرسائل الحرفية التي تُشفَّر إلى s

القيود

1 ≤ s.length ≤ 100
s يحتوي فقط على الأرقام من 0 إلى 9، وقد يبدأ بـ 0.
كل بادئة وكل لاحقة من s لها أقل من 2³¹ قراءة، لذا فإن الإجابة وكل عدد تحسبه أثناء ذلك يتسع في عدد صحيح موقّع ذي 32 بتًا.

أمثلة

المدخلات: s = "2611"
المخرجات: 4
الشرح: القراءات الأربع هي 2 6 1 1 (BFAA)، و26 1 1 (ZAA)، و2 6 11 (BFK)، و26 11 (ZK). لا يقترن الرقمان الأوسطان أبدًا، لأن 61 أكبر من 26.

المدخلات: s = "1203"
المخرجات: 1
الشرح: يجب أن يقترن 0 بـ 2 الذي يسبقه ليشكّلا 20، وهذا يفرض 1 20 3 (ATC). قراءة 12 أولًا ستترك 0 بمفرده، و03 يبدأ بـ 0.

المدخلات: s = "06"
المخرجات: 0
الشرح: يجب أن يبدأ الحرف الأول بـ 0. لا يُعدّ 0 المنفرد حرفًا، و06 ليس رمزًا، لذا لا توجد رسالة تعطي هذه السلسلة.

سؤال إضافي

ماذا لو كان بإمكان s أن يحتوي أيضًا على *، التي تمثل أي رقم من 1 إلى 9؟ هل يمكنك حساب عدد القراءات في زمن O(n)، بترديد 10^9+7؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

يمكن أن يكون كل رقم حرفًا بمفرده أو ينضم إلى الرقم المجاور له، لذا يزداد عدد القراءات مثل أعداد فيبوناتشي: لـ45 رقمًا من الرقم 1 عددٌ قدره 1836311903 قراءة. حصرها أمر مستحيل، لكن طرق إكمال القراءة تعتمد فقط على الموضع الذي وصلت إليه، لذا يكفي عدّ كل موضع مرة واحدة. لا يمكن أن يأتي 0 إلا في نهاية 10 أو 20.

جرّب القراءتين باستخدام الاستدعاء الذاتي

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

عند الفهرس i، لا يبدأ 0 أي حرف، لذا لا يعطي المسار أي قراءات. بخلاف ذلك، اقرأ رقمًا واحدًا واحسب الباقي بدءًا من i+1؛ وإذا كان الرقمان يشكّلان عددًا من 10 إلى 26، فاقرأهما معًا أيضًا واحسب بدءًا من i+2. يعطي الخياران حرفين أولين مختلفين، لذا نجمع عدديهما دون تداخل، والوصول إلى النهاية يُكمل قراءة واحدة.

لا يتم تذكّر أي شيء، لذا تتبع الاستدعاءات قاعدة فيبوناتشي: تستغرق 45 واحدًا نحو 5 × 10^9 استدعاء. والإجابة 0 ليست أسرع: إذ تستغرق 44 واحدًا و55 ثلاثةً و0 أخير نحو 10^11 استدعاء، لأن كل قراءة للأرقام 1 لا تنتهي إلا عند الرقم الأخير.

الخوارزمية

تحسب waysFrom(i) عدد طرق قراءة الأرقام بدءًا من الفهرس i.
عند نهاية السلسلة، أعد 1. وعند وجود 0، أعد 0.
وإلا فأعد waysFrom(i+1)، بالإضافة إلى waysFrom(i+2) عندما يشكّل الرقمان عند i وi+1 عددًا لا يتجاوز 26.
الإجابة هي waysFrom(0).

def numDecodings(s):
    n = len(s)

    def ways_from(i):
        # The number of ways to decode s[i:].
        if i == n:
            return 1  # nothing left: one finished reading
        if s[i] == "0":
            return 0  # no letter code starts with 0
        ways = ways_from(i + 1)  # read one digit
        if i + 1 < n and int(s[i:i + 2]) <= 26:
            ways += ways_from(i + 2)  # read two digits, 10 to 26
        return ways

    return ways_from(0)

الاستدعاء الذاتي باستخدام مذكرة

الفكرة

يطرح الاستدعاء العودي السؤال نفسه مرات عديدة. في "11111"، نحتاج إلى العدد بدءًا من الفهرس 3 بعد 1 1 1، وبعد 11 1، وبعد 1 11، ويكون العدد نفسه في كل مرة، لأنه يعتمد فقط على الأرقام ابتداءً من الفهرس 3. خزّن كل عدد عند حسابه أول مرة، وعلّم الخانات التي لم تُحسب بعد بالقيمة -1، لأن 0 عدد حقيقي.

هناك n مواضع، ويُحسب كل منها مرة واحدة بعمل ثابت: زمن O(n). تشغل الذاكرة المؤقتة ومكدس الاستدعاءات مساحة O(n)، وبعمق يصل إلى 100 استدعاء كحد أقصى.

الخوارزمية

املأ memo بالقيمة -1، خانة واحدة لكل فهرس.
في waysFrom(i)، أعد 1 عند نهاية السلسلة، وأعد memo[i] إذا لم تكن قيمته -1.
وإلا فاحسب العدد كما في الاستدعاء الذاتي البسيط، واحفظ العدد في memo[i]، بما في ذلك الصفر، ثم أعده.

def numDecodings(s):
    n = len(s)
    memo = [-1] * n  # memo[i]: ways to decode s[i:], -1 until worked out

    def ways_from(i):
        if i == n:
            return 1
        if memo[i] != -1:
            return memo[i]
        ways = 0
        if s[i] != "0":
            ways = ways_from(i + 1)  # read one digit
            if i + 1 < n and int(s[i:i + 2]) <= 26:
                ways += ways_from(i + 2)  # read two digits, 10 to 26
        memo[i] = ways
        return ways

    return ways_from(0)

من الأسفل إلى الأعلى باستخدام عدّادين

الفكرة

بدلًا من ذلك، احسب البادئات. لتكن ways(i) عدد طرق قراءة أول i من الأرقام. الحرف الأخير إما الرقم i-1 وحده، وهو ما يتطلب أن يكون من 1 إلى 9 ويترك ways(i-1) طريقة للقراءة، أو الرقمان i-2 وi-1 معًا، ويجب أن يشكّلا عددًا من 10 إلى 26 ويتركا ways(i-2). اجمع الأجزاء التي يتحقق شرطها. للبادئة الفارغة طريقة قراءة واحدة، لذا ways(0) = 1.

في "1203"، تتتابع الأعداد: 1، 2، ثم تعود إلى 1 عند 0، لأن 20 وحده صالح، وهو يترك العدد السابق للرقم 2. أما 3 فيأتي منفردًا، لذا يبقى العدد 1. يعتمد كل عدد على ما يسبقه بموقعين، لذا يحل متغيران محل الجدول: زمن O(n) ومساحة O(1).

الخوارزمية

عيّن twoBack = 0 وoneBack = 1، وهو العدد الخاص بالبادئة الفارغة.
لكل فهرس i، عيّن current إلى oneBack إذا لم يكن الرقم i هو 0، وإلا فإلى 0.
إذا كان i ≥ 1، وكان الرقم i-1 ليس 0، وشكّل الرقمان i-1 وi عددًا لا يتجاوز 26، فأضف twoBack.
حدّث القيم: twoBack = oneBack، ثم oneBack = current.
أعِد oneBack.

def numDecodings(s):
    # ways(i) counts the readings of the first i digits; ways(0) = 1.
    two_back, one_back = 0, 1  # ways(i-1) and ways(i) before digit i is read
    for i in range(len(s)):
        current = 0
        if s[i] != "0":
            current = one_back  # digit i is a letter on its own
        if i >= 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
            current += two_back  # digits i-1 and i form one letter, 10 to 26
        two_back, one_back = one_back, current
    return one_back

أخطاء شائعة وحالات حدّية

اعتبار 0 حرفًا، أو اعتبار 06 مساويًا لـ 6. جميع القيم "30" و"100" و"06" لها 0 قراءات.
اختبار جزء مكوّن من رقمين باستخدام ≤ 26 وحده. 05 يساوي 5 كعدد، لكنه ليس رمزًا، لذا تحقّق من أن رقمه الأول ليس 0.
وضع 0 في خانات التخزين المؤقت غير المعروفة. عندها لا تُحتسب المواضع ذات 0 قراءة على أنها مخزّنة أبدًا: مع 44 واحدًا و55 ثلاثةً وصفر أخير، تعود إلى نحو 10^11 استدعاء.
قراءة الرقم السابق للفهرس 0. اجعل فحص الرقمين مشروطًا بـ i ≥ 1؛ ففي Python، تقرأ s[-1] الرقم الأخير بصمت.
تحويل s إلى عدد واحد. لا يتّسع أي نوع أعداد صحيحة لمئة رقم، كما تُفقد الأصفار البادئة التي تغيّر الإجابة.

أسئلة شائعة3

ما هو التعقيد الزمني لمسألة Decode Ways؟

يقرأ الحل من الأسفل إلى الأعلى كل رقم مرة واحدة بعمل ثابت: زمن O(n) ومساحة إضافية O(1). كما أن الاستدعاء الذاتي مع التخزين المؤقت يستغرق زمن O(n) لكنه يستخدم مساحة O(n). أما الاستدعاء الذاتي العادي فأُسّي: في سلسلة من الواحدات، يزداد عدد الاستدعاءات بمعدل يقارب 1.618^n.

ما العلاقة بين مسألة فك ترميز الطرق ومسألة صعود الدرج؟

كلاهما يحسب عدد طرق تغطية خط بخطوات طولها 1 و2. في مسألة تسلّق الدرج، كل خطوة مسموح بها، لذا تكون الأعداد هي أعداد فيبوناتشي. في مسألة فك الترميز، تتطلب الخطوة المكوّنة من رقم واحد أن يكون الرقم من 1 إلى 9، وتتطلب الخطوة المكوّنة من رقمين أن يكون العدد من 10 إلى 26، لذا يُضاف كل حد فقط عند تحقق شرطه.

كيف تتعامل مع الأصفار في Decode Ways؟

لا يكون 0 حرفًا بمفرده أبدًا، لذا يجب أن يقترن بالرقم الذي قبله مثل 10 أو 20. وهو يضيف العدد من خانتين إلى الوراء فقط بعد 1 أو 2، ولا يفعل ذلك في غير هذه الحالة. ويعطي 0 في البداية، أو صفران متتاليان، أو 0 بعد رقم من 3 إلى 9.

def numDecodings(s):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

s = "2611"

الإخراج المتوقع

Decode Ways

الدالة

القيود

أمثلة

تلميحات

الحل

جرّب القراءتين باستخدام الاستدعاء الذاتي

الاستدعاء الذاتي باستخدام مذكرة

من الأسفل إلى الأعلى باستخدام عدّادين

أخطاء شائعة وحالات حدّية

أسئلة شائعة3

مسائل مشابهة