Decode Ways

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

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

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

+10

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

تُقرأ كلّ رسالة حرفًا واحدًا من رقم واحد أو من رقمين متجاورين، ولا يبدأ أي ترميز بـ 0: فـ 06 لا تساوي 6، كما أن 0 بمفرده ليس حرفًا. إذا لم تنجح أي قراءة، فأَعِد 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 ليس رمزًا، لذا لا تعطي أي رسالة هذه السلسلة.

+25 اختبارات مخفية عند الإرسال

سؤال إضافي

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

تلميحات

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

فُتح 0 من 3

الحل

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

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

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

الفكرة

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

في "2611": الحرف الأول هو 2 أو 26. بعد 2، يجب أن يكون الحرف التالي 6، لأن 61 أكبر من اللازم. ثم ينتهي كلا الفرعين بـ 1 1 أو 11، لذا يكون المجموع 2 × 2 = 4.

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

الخوارزمية

اكتب دالة مساعدة waysFrom(i) تحسب طرق قراءة الأرقام بدءًا من الفهرس i حتى النهاية.
إذا كان i يساوي طول s، فأعِد 1.
إذا كان الرقم عند i هو 0، فأعِد 0.
ابدأ بـ waysFrom(i+1)، وهي القراءات التي يكون فيها الحرف التالي ممثلًا برقم واحد.
إذا شكّل الرقمان عند i وi+1 عددًا لا يتجاوز 26، فأضف waysFrom(i+2). أَعِد 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 فصاعدًا. خزّن كل عدد في مصفوفة memo في المرة الأولى التي تحسبه فيها، واقرأه منها بعد ذلك.

علِّم الخانات التي لم يُحسب ناتجها بعد بالقيمة -1، لا بـ 0. الصفر إجابة فعلية هنا: في سلسلة تنتهي بـ 30، يكون عدد القراءات 0 في كل موضع. وعند استخدام 0 كعلامة، تبدو تلك المواضع مجهولة عند كل زيارة، ويظل الاستدعاء الذاتي بطيئًا كما كان من قبل.

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

الخوارزمية

أنشئ مصفوفة memo تحتوي على خانة لكل فهرس، واجعل قيمة جميع الخانات -1.
في waysFrom(i)، أرجِع 1 عند نهاية السلسلة، وأرجِع memo[i] عندما لا تكون قيمته -1.
وإلا، فاحسب كما في الاستدعاء الذاتي البسيط: 0 إذا كان الرقم 0، وإلا فاجمع waysFrom(i+1) وwaysFrom(i+2) عندما يشكّل الرقمان عددًا من 10 إلى 26.
احفظ العدد في memo[i]، حتى لو كان صفرًا، ثم أرجِعه.
أرجِع waysFrom(0).

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(i) هو مجموع الأجزاء التي يتحقق شرطها. للبادئة الفارغة قراءة واحدة، وهي الرسالة الفارغة، لذا ways(0) = 1.

تتبّع "1203". بعد 1 يكون العدد 1. بعد 12 يكون 2: 1 2 و12. لا يمكن أن يأتي 0 منفردًا، ولا يصلح إلا 20، لذا ينخفض العدد إلى العدد الذي كان قبل 2، وهو 1. يأتي 3 منفردًا، و03 ليس رمزًا، لذا يبقى العدد 1.

يعتمد كل عدد على العددين السابقين فقط، لذا يحل المتغيران twoBack وoneBack محل الجدول. هذه عملية مرور واحدة بعمل ثابت لكل رقم: زمن O(n)، ومساحة O(1)، ومن دون أي استدعاء ذاتي.

الخوارزمية

عيّن twoBack = 0 وoneBack = 1، وهو عدد البادئة الفارغة.
لكل فهرس i، ابدأ current بالقيمة 0، وأضف oneBack إذا لم يكن الرقم i هو 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. لا يمكن للصفر أن يأتي إلا في نهاية 10 أو 20، لذا فإن "30" و"100" و"06" جميعها لها 0 من القراءات.
اختبار مقطع من رقمين باستخدام ≤ 26 وحده. إن 05 يساوي 5 كعدد، لكنه ليس رمزًا. تحقّق من أن الرقم الأول من الرقمين ليس 0.
استخدام 0 علامةً لخانة في الذاكرة المؤقتة لم تُحسب بعد. فهناك مواضع كثيرة لها فعلًا 0 من القراءات، لذلك لا تُحسب تلك الخانات على أنها مخزنة، ويُعاد حسابها عند كل زيارة. في سلسلة من 44 رقمًا واحدًا يتبعها أرقام ثلاثة وتنتهي بـ 0، تكون كل الخانات 0، وتعود إلى نحو 10^11 استدعاء.
قراءة الرقم السابق للفهرس 0. اجعل فحص الرقمين مشروطًا بـ i ≥ 1: في Python تقرأ s[-1] الرقم الأخير بصمت، بينما تقرأ اللغات الأخرى من خارج السلسلة.
تحويل s إلى عدد واحد. لا يتسع أي نوع أعداد صحيحة لمئة رقم، كما أن التحويل يحذف الأصفار البادئة التي تغيّر الإجابة. عالج الأرقام واحدًا تلو الآخر.
في Lua وR، تبدأ المواضع من 1، لذا فإن نهاية السلسلة هي الموضع n+1، ويكون أول فحص لرقمين عند الموضع 2.

أسئلة شائعة4

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

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

ما العلاقة بين Decode Ways وتسلق السلالم؟

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

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

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

هل يمكن حل مسألة فك الترميز (Decode Ways) باستخدام مساحة O(1)؟

نعم. يعتمد عدد كل بادئة فقط على عددي البادئتين الأقصر منها برقم واحد ورقمين، لذا يحل متغيران محل الجدول بأكمله. تحسب كل خطوة العدد الجديد منهما، ثم تحرّكهما موضعًا واحدًا إلى الأمام.

Python

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

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

s = "2611"

المتوقع

Decode Ways

الدالة

القيود

أمثلة

تلميحات

الحل

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

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

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

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

أسئلة شائعة4

مسائل مشابهة