String Compression

Q: ما التعقيد الزمني لضغط السلاسل النصية؟

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

سهلمؤشران المصفوفات والسلاسل النصية

+10

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

الأحرف الكبيرة والصغيرة مختلفة: aA عبارة عن تتابعين، طول كل منهما 1.

الدالة

compress(s: string) → string

sstring: السلسلة النصية المراد ضغطها، أحرف إنجليزية فقط
تُرجعstring: السلسلة المضغوطة، حيث يُكتب كل تكرار على شكل حرفه متبوعًا بطوله إذا كان الطول أكبر من 1

القيود

1 ≤ s.length ≤ 2 × 10⁴
s يحتوي على أحرف إنجليزية فقط، من a إلى z ومن A إلى Z.
يُكتب طول التشغيل بالنظام العشري، ويمكن أن يتكوّن من عدة أرقام.

أمثلة

المدخلات: s = "aabccc"
المخرجات: "a2bc3"
الشرح: المقاطع هي aa وb وccc. تصبح a2 وb (لا يُضاف عدد إلى الحرف المنفرد) وc3.

المدخلات: s = "abbbbbbbbbbbb"
المخرجات: "ab12"
الشرح: حرف a واحد، ثم اثنا عشر حرفًا b. يُكتب الطول 12 بالحرفين 1 و2، لذا تكون النتيجة ab12.

المدخلات: s = "zzZZZ"
المخرجات: "z2Z3"
الشرح: الحرف z الصغير والحرف Z الكبير حرفان مختلفان، لذا فهذا تتابع من اثنين يتبعه تتابع من ثلاثة: z2Z3.

سؤال إضافي

اكتب العملية العكسية: انطلاقًا من سلسلة مضغوطة مثل ab12، أعد بناء السلسلة الأصلية. كيف تقرأ عددًا يتكوّن من عدة أرقام؟

تلميحات

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

فُتح 0 من 3

الحل

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

اجمع عمليات التشغيل، ثم اكتبها

الفكرة

سجّل أولًا التتابعات على شكل أزواج من حرف وطول: في aabccc، (a, 2)، (b, 1)، (c, 3). إمّا أن يمدّد كل حرف التتابع الأخير أو يبدأ تتابعًا جديدًا. ثم اكتب حرف كل تتابع، متبوعًا بطوله إذا كان أكبر من 1.

كلا المرورين O(n). قد تحتوي القائمة على n تتابعات عندما لا يتطابق أي حرفين متجاورين، لذا تتطلب مساحة إضافية مقدارها O(n).

الخوارزمية

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

def compress(s):
    # First pass: collect the runs as [letter, length] pairs
    runs = []
    for ch in s:
        if runs and runs[-1][0] == ch:
            runs[-1][1] += 1
        else:
            runs.append([ch, 1])
    # Second pass: write each run, with its length when it is more than 1
    parts = []
    for letter, length in runs:
        parts.append(letter)
        if length > 1:
            parts.append(str(length))
    return "".join(parts)

مؤشران لكل تتابع

الفكرة

أبقِ i عند الحرف الأول من المقطع الحالي، وحرّك j إلى الأمام ما دام s[j] يساوي s[i]. عندما يتوقف j، عند حرف مختلف أو عند النهاية، يكون طول المقطع هو j-i. اكتبه واجعل i = j. في abbbbbbbbbbbb، يتوقف j أولًا عند 1، فيعطي a، ثم عند 13، فيعطي b12.

لا يحتاج المقطع الأخير إلى حالة خاصة، لأن الحلقة الداخلية تتوقف عند نهاية السلسلة. يتحرك j إلى الأمام فقط، لذا فالزمن هو O(n)، وإلى جانب النتيجة، تحتفظ بمؤشرين. تقسّم نسختا R وSwift الرمز s إلى مصفوفة من المحارف أولًا، لذا تستخدمان مساحة إضافية قدرها O(n).

الخوارزمية

عيّن i = 0.
طالما أن i داخل السلسلة النصية، عيّن j = i وحرّك j إلى الأمام ما دام داخل السلسلة النصية وs[j] يساوي s[i].
اكتب s[i]؛ وإذا كان j-i أكبر من 1، فاكتبه كنص عشري.
عيّن i = j وكرّر.

def compress(s):
    parts = []
    n = len(s)
    i = 0
    while i < n:
        # Move j to the first index after the run that starts at i
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        parts.append(s[i])
        if j - i > 1:
            parts.append(str(j - i))
        i = j
    return "".join(parts)

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

كتابة مجموعة متتالية فقط عند مواجهة حرف مختلف. لا شيء يأتي بعد ccc الأخيرة في aabccc، لذا تُرجع a2b.
كتابة العدد بحرف واحد، مثل '0' + count. يتعطل ذلك عند 10: فاثنا عشر حرفًا من b تحتاج إلى الحرفين 12.
كتابة 1 بعد حرف منفرد. يبقى b كما هو b، وليس b1.
تجاهل حالة الأحرف. تكون zzZZZ هي z2Z3، وليست z5.
تنمية سلسلة غير قابلة للتغيير باستخدام +، كما في Java أو C#. تنسخ كل + النتيجة حتى تلك اللحظة، ما يجعل الحلقة O(n²)؛ استخدم منشئ السلاسل.

أسئلة شائعة3

ما التعقيد الزمني لضغط السلاسل النصية؟

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

هل يمكن أن تكون السلسلة المضغوطة أطول من السلسلة الأصلية؟

ليس في هذا الإصدار. يظل الحرف المنفرد حرفًا واحدًا، ويتحوّل تسلسل من الأحرف طوله k ≥ 2 إلى حرف واحد مع أرقام k، ولا يتجاوز أبدًا k أحرف. أما المخطط الذي يكتب عددًا بعد كل حرف، مثل a1b1، فقد يضاعف الطول.

كيف تضغط سلسلة نصية في مكانها؟

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

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

اختبار #1

اختبار #2

اختبار #3

وسيط

s = "aabccc"

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

"a2bc3"