Decode String

Q: كيف تتعامل مع الأعداد التي تتكوّن من أكثر من رقم واحد؟

كوِّن العدد أثناء قراءته: ابدأ من 0، ولكل رقم عيّن count = count × 10 + digit . عندما يصل [ يكتمل العدد، لذا فإن 300[a] تعطي 300. أعد تعيين count إلى 0 بمجرد دفعه، وإلا فستُضاف أرقام المجموعة التالية إليه.

Q: لماذا يخزّن المكدس النص الذي يسبق كل قوس؟

عندما يفتح [ ، لا يكون النص الذي فُك ترميزه حتى تلك المرحلة عند هذا المستوى مكتملًا: فما زال يجب إلحاق نسخ المجموعة به. يضمن دفعه إلى المكدس بقاءه محفوظًا أثناء فك ترميز المحتوى بدءًا من سلسلة فارغة. وعندما يصل ] المطابق، يعيد سحبه ذلك النص، ثم تُلحق به النسخ.

متوسطالمكدس العودية

+10

تكتب السلسلة المُرمَّزة النص المتكرر على هيئة k[text]، وهذا يعني كتابة text عدد k من المرات متتالية. يمكن أن تكون المجموعات متداخلة، لذا فإن 2[a3[b]] تعني abbbabbb. اكتب دالة تستقبل سلسلة مُرمَّزة s وتُرجع السلسلة بعد فك ترميزها.

تبقى الأحرف الواقعة خارج جميع الأقواس كما هي. كل عدد هو عدد صحيح موجب يُكتب مباشرة قبل [، ولا تظهر الأرقام في أي موضع آخر.

الدالة

decodeString(s: string) → string

sstring: السلسلة النصية المُرمَّزة
تُرجعstring: السلسلة النصية المُفكَّكة

القيود

1 ≤ s.length ≤ 10⁴
s يحتوي على أحرف إنجليزية صغيرة وأرقام و[ و].
s ترميز صالح: يتبع كل [ عددٌ، وله ] مطابق، ولا توجد أقواس فارغة.
كل عدد k يحقق 1 ≤ k ≤ 300 ولا يحتوي على صفر بادئ.
تتداخل الأقواس بعمق يصل إلى 100 مستوى كحد أقصى.
يحتوي النص بعد فك ترميزه على 5 × 10⁴ أحرف على الأكثر.

أمثلة

المدخلات: s = "2[ab]3[c]x"
المخرجات: "ababcccx"
الشرح: يعطي 2[ab] النتيجة abab، ويعطي 3[c] النتيجة ccc. يقع x خارج جميع الأقواس، لذا يُنسخ كما هو، ما يعطي ababcccx.

المدخلات: s = "2[x3[yz]]"
المخرجات: "xyzyzyzxyzyzyz"
الشرح: فكّ ترميز الجزء الداخلي أولًا: 3[yz] هو yzyzyz، لذا يكون محتوى المجموعة الخارجية xyzyzyz. وعند كتابته مرتين، يصبح xyzyzyzxyzyzyz.

المدخلات: s = "q10[w]e"
المخرجات: "qwwwwwwwwwwe"
الشرح: العدد هو 10، ويُقرأ من رقمين، لذا يظهر w عشر مرات بين q وe. أما الكود الذي يقرأ الرقم المجاور لـ [ فقط، فسيكرره 0 مرة.

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

سؤال إضافي

قد تكون السلسلة المفككة أطول بكثير من المُدخل. كيف ستُعيد الحرف الموجود في الموضع i من السلسلة المفككة فقط، من دون بنائها، عندما يمكن أن يصل طولها إلى 10^18؟

تلميحات

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

فُتح 0 من 3

الحل

يأتي العدد قبل الأقواس، لكن لا يمكنك كتابة النسخ قبل أن تعرف ما بداخلها، وقد يحتوي ما بداخلها على مجموعات أخرى. لذا لا يمكن توسيع المجموعة إلا بعد الانتهاء من كل مجموعة بداخلها. كل طريقة أدناه هي أسلوب لإنهاء المجموعات الأعمق أولًا: أعد كتابة السلسلة من الداخل إلى الخارج، أو دع استدعاءً递يًا يُنهي المجموعة الداخلية قبل الخارجية، أو احتفظ بالمجموعات الخارجية غير المكتملة على مكدس. أدناه، n هو طول الإدخال، وm طول السلسلة بعد فك الترميز، وd أعمق مستوى من التداخل.

وسّع المجموعة الأعمق، ثم كرّر

الفكرة

فكّ ترميز السلسلة بالطريقة التي ستتبعها على الورق. ابحث عن مجموعة لا توجد داخلها أي مجموعة أخرى، واكتب نسخها في موضعها، ثم ألقِ نظرة أخرى. في 2[x3[yz]]، لا تحتوي المجموعة 3[yz] على أي شيء بداخلها، لذا تصبح السلسلة 2[xyzyzyz]، ويعطي التوسيع مرة أخرى الإجابة.

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

هذا صحيح، لكن كل عملية توسيع تعيد إنشاء السلسلة بأكملها. مع وجود b مجموعة وسلسلة يزداد طولها حتى m حرفًا، يصل عدد نسخ الأحرف إلى b × m. تستغرق حالة الاختبار المخفية، التي تضم نحو 1,300 مجموعة متجاورة، حوالي 25 مليون عملية نسخ لإنتاج 27,688 حرفًا، بينما تكفي قراءة واحدة للمدخلات.

الخوارزمية

اعثر على أول ] في السلسلة. إذا لم يوجد، تكون السلسلة مفكوكة الترميز: أعدها.
تحرّك إلى اليسار منه حتى أقرب [. النص بينهما هو محتوى المجموعة.
تحرّك أكثر إلى اليسار متجاوزًا الأرقام التي تسبق ذلك [، واقرأها بوصفها العدد k.
استبدل كل شيء من الرقم الأول إلى ] بمحتوى المجموعة مكتوبًا k مرة.
عُد إلى الخطوة 1.

def decodeString(s):
    # Expand one innermost group at a time until no bracket is left.
    while True:
        close = s.find("]")
        if close == -1:
            return s
        # The first ']' closes a group with no group inside it,
        # and the nearest '[' to its left opens that group.
        open_ = s.rfind("[", 0, close)
        start = open_
        while start > 0 and s[start - 1].isdigit():
            start -= 1
        times = int(s[start:open_])
        s = s[:start] + s[open_ + 1:close] * times + s[close + 1:]

التحليل التنازلي العودي

الفكرة

التنسيق تكراري: السلسلة المُرمَّزة هي تسلسل من الأحرف والمجموعات، ومحتوى المجموعة هو بدوره سلسلة مُرمَّزة. لذا اكتب دالة واحدة، decode، تقرأ من موضع مشترك حتى تصل إلى ] الذي ينهي مستواها أو إلى نهاية الإدخال، ثم تعيد ما قرأته بعد فك ترميزه.

عندما تصادف decode رقمًا، تقرأ العدد كاملًا، وتتجاوز [، ثم تستدعي نفسها لفك ترميز المحتوى. يتوقف هذا الاستدعاء عند ] المطابقة، لأن أي ] أعمق قد استهلكه بالفعل استدعاء أعمق. يتجاوز الاستدعاء المستدعي ]، ويضيف المحتوى k مرات، ثم يواصل القراءة. في 2[x3[yz]]، يقرأ الاستدعاء الخارجي 2؛ ويقرأ الاستدعاء التالي x و3؛ ويعيد استدعاء ثالث yz؛ ويعيد الاستدعاء الأوسط xyzyzyz؛ ثم يكتب الاستدعاء الخارجي الناتج مرتين.

تُقرأ كل محرف من الإدخال مرة واحدة. أما الكلفة الفعلية فتأتي من النسخ: يُنسخ محرف من الناتج مرةً لكل مجموعة تحيط به، لذا يكون الزمن O(n + m·d)، حيث d هو عمق التداخل. كما يصل عمق الاستدعاء التكراري إلى d. وهذا مقبول عند 100 مستوى، لكن الإدخال شديد العمق قد يفيض بمكدس الاستدعاءات: فـ Python، على سبيل المثال، يتوقف افتراضيًا عند 1,000 استدعاء متداخل.

الخوارزمية

احتفِظ بموضع واحد pos مشترك بين كل الاستدعاءات، يبدأ عند الحرف الأول.
تكرّر decode() ما دام pos داخل السلسلة وليس عند ].
عند مواجهة حرف، ألحِقه وانتقل إلى التالي.
عند مواجهة رقم، اقرأ العدد كاملًا k، وتجاوز [، واستدعِ decode() لمعالجة المحتوى، وتجاوز ]، وألحِق المحتوى k مرات.
أعِد ما تم بناؤه. يُعيد الاستدعاء الأول السلسلة المفككة.

def decodeString(s):
    pos = 0

    def decode():
        # Read from pos up to the ']' that closes this level, or the end.
        nonlocal pos
        parts = []
        while pos < len(s) and s[pos] != "]":
            if s[pos].isdigit():
                times = 0
                while s[pos].isdigit():
                    times = times * 10 + int(s[pos])
                    pos += 1
                pos += 1          # skip '['
                inner = decode()  # the group's body, fully decoded
                pos += 1          # skip ']'
                parts.append(inner * times)
            else:
                parts.append(s[pos])
                pos += 1
        return "".join(parts)

    return decode()

تمريرة واحدة باستخدام مكدّس

الفكرة

يحتفظ الاستدعاء الذاتي بقطعة نص غير مكتملة لكل مجموعة مفتوحة داخل إطارات الاستدعاء الخاصة به. يمكنك بدلًا من ذلك الاحتفاظ بهذه القطع في مكدس خاص بك وقراءة السلسلة في حلقة واحدة.

تابع شيئين للمستوى الحالي: current، النص الذي فُك ترميزه حتى الآن، وcount، العدد الذي تجري قراءته. يضيف الرقم إلى count وفقًا للمعادلة count × 10 + digit، لذا تكون النتيجة صحيحة مع 10 و300. يفتح [ مستوىً جديدًا: ادفع current وcount إلى المكدس، ثم ابدأ من جديد بكليهما. يُضاف الحرف إلى current. يُغلق ] المستوى: اسحب النص والعدد المحفوظين، واجعل current يساوي النص المحفوظ متبوعًا بنسخ من current بعدد count.

تتبّع 2[x3[yz]]. عند أول [، تدفع (فارغ، 2) إلى المكدس. يجعل x قيمة current تساوي x. عند ثاني [، تدفع (x، 3)، ويملأ yz قيمة current جديدة. يسحب أول ] (x، 3)، فتصبح قيمة current xyzyzyz. يسحب آخر ] (فارغ، 2)، وتصبح قيمة current xyzyzyzxyzyzyz.

تُغلق المجموعات بترتيب عكسي لترتيب فتحها، لذا يكون العنصر الموجود أعلى المكدس دائمًا هو المستوى الذي يعود إليه ]. يظل مقدار العمل مماثلًا للاستدعاء الذاتي، O(n + m·d)، لكن التداخل العميق لا يؤدي إلا إلى زيادة حجم قائمة، ولا يزيد أبدًا من عمق مكدس الاستدعاء.

الخوارزمية

ابدأ بمكدس فارغ، وcurrent فارغ، وcount = 0.
عند قراءة رقم، عيّن count = count × 10 + digit.
عند قراءة [، ادفع الزوج (current، count) إلى المكدس، ثم أعد تعيين current إلى فارغ وcount إلى 0.
عند قراءة حرف، أضِفه إلى current.
عند قراءة ]، أخرج (before، k) من المكدس، وعيّن current إلى before متبوعًا بـ k نسخ من current.
بعد آخر حرف، أعد current.

def decodeString(s):
    stack = []      # one entry per open '[': (the text before it, its count)
    current = []    # pieces of the text at the current level
    count = 0
    for ch in s:
        if ch.isdigit():
            count = count * 10 + int(ch)   # counts can have several digits
        elif ch == "[":
            stack.append((current, count))
            current, count = [], 0
        elif ch == "]":
            before, times = stack.pop()
            before.append("".join(current) * times)
            current = before
        else:
            current.append(ch)
    return "".join(current)

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

تنتج معظم الإجابات الخاطئة عن قراءة العدد أو عن موضع إضافة النص المحفوظ.

قراءة رقم واحد على أنه العدد كله. في q10[w]e العدد هو 10. الشيفرة التي تأخذ الرقم الذي يسبق [ فقط تكرر w صفر مرة.
نسيان إعادة count إلى 0 بعد دفعه إلى المكدس. عندئذٍ تُضاف أرقام المجموعة التالية إلى العدد القديم، لذا تُقرأ قيمة العدد داخل 2[a3[b]] على أنها 23.
وضع النسخ قبل النص المحفوظ. عند الوصول إلى ] تكون النتيجة هي النص السابق للمجموعة متبوعًا بالنسخ، لذا تكون ab2[c] هي abcc، وليست ccab.
فقدان الأحرف على المستوى الأعلى. يقع الحرف x في 2[ab]3[c]x خارج جميع الأقواس، ومع ذلك يجب أن يكون ضمن الإجابة.
إضافة حرف واحد في كل مرة إلى سلسلة طويلة غير قابلة للتغيير. قد تؤدي كل إضافة إلى نسخ السلسلة بأكملها، فتحوّل إجابة من 50,000 حرف إلى مليارات النسخ. اجمع الأجزاء في قائمة أو في أداة لبناء السلاسل.

أسئلة شائعة4

ما هو التعقيد الزمني لفك ترميز سلسلة نصية؟

تستغرق قراءة الإدخال O(n). وينسخ بناء الناتج كل حرف مرةً واحدةً لكل مجموعة يقع ضمنها، لذا يكون الإجمالي O(n + m·d)، حيث m هو الطول بعد فك الترميز وd هو عمق التداخل. عندما يكون كل عدد 2 على الأقل، لا يتجاوز طول أي مجموعة نصف طول المجموعة المحيطة بها، لذا يبقى النسخ أقل من 2m. لا يمكن لأي طريقة أن تتجاوز O(m)، لأن الإجابة نفسها تتكون من m حرفًا.

هل ينبغي أن تحل مسألة فك ترميز السلسلة باستخدام الاستدعاء الذاتي أم باستخدام مكدس؟

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

كيف تتعامل مع الأعداد التي تتكوّن من أكثر من رقم واحد؟

كوِّن العدد أثناء قراءته: ابدأ من 0، ولكل رقم عيّن count = count × 10 + digit. عندما يصل [ يكتمل العدد، لذا فإن 300[a] تعطي 300. أعد تعيين count إلى 0 بمجرد دفعه، وإلا فستُضاف أرقام المجموعة التالية إليه.

لماذا يخزّن المكدس النص الذي يسبق كل قوس؟

عندما يفتح [، لا يكون النص الذي فُك ترميزه حتى تلك المرحلة عند هذا المستوى مكتملًا: فما زال يجب إلحاق نسخ المجموعة به. يضمن دفعه إلى المكدس بقاءه محفوظًا أثناء فك ترميز المحتوى بدءًا من سلسلة فارغة. وعندما يصل ] المطابق، يعيد سحبه ذلك النص، ثم تُلحق به النسخ.

Python

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

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

الحالة 1

الحالة 2

الحالة 3

المدخلات

s = "2[ab]3[c]x"

المتوقع

"ababcccx"

Decode String

الدالة

القيود

أمثلة

تلميحات

الحل

وسّع المجموعة الأعمق، ثم كرّر

التحليل التنازلي العودي

تمريرة واحدة باستخدام مكدّس

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

أسئلة شائعة4

مسائل مشابهة