Group Anagrams

+10

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

تُدرج الكلمة التي تظهر مرتين مرتين في مجموعتها، والكلمة التي لا تملك كلمةً مطابقة لها من حيث الحروف تشكّل مجموعةً من كلمة واحدة. والترتيب الأبجدي يعني ترتيب القاموس: تأتي aab قبل ab، وab قبل abc.

الدالة

groupAnagrams(strs: string-array) → string-array

strsstring-array: الكلمات للتجميع، أحرف صغيرة فقط
تُرجعstring-array: سلسلة نصية واحدة لكل مجموعة: تُرتَّب كلماتها وتُوصَل بمسافات، وتُرتَّب المجموعات حسب كلمتها الأولى

القيود

1 ≤ strs.length ≤ 4000
1 ≤ strs[i].length ≤ 8
تتكوّن كل كلمة من أحرف إنجليزية صغيرة فقط.

أمثلة

المدخلات: strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
المخرجات: ["apple", "enlist listen silent", "notes onset stone tones"]
الشرح: تستخدم كل من enlist وlisten وsilent الأحرف e وi وl وn وs وt مرة واحدة. وتشترك notes وonset وstone وtones في الأحرف e وn وo وs وt، ولا تطابق apple أي شيء. وبحسب الكلمة الأولى، تكون المجموعات بالترتيب apple وenlist وnotes.

المدخلات: strs = ["race", "arc", "care", "car", "acre"]
المخرجات: ["acre care race", "arc car"]
الشرح: تشترك acre وcare وrace في الأحرف a وc وe وr. لا تحتوي arc وcar على الحرف e، لذا تشكّلان مجموعتهما الخاصة. تأتي acre قبل arc لأن c تسبق r في الحرف الثاني.

المدخلات: strs = ["b", "a", "b"]
المخرجات: ["a", "b b"]
الشرح: النسختان من b متطابقتان في الحروف، وتبقيان كلتاهما في المجموعة. ليس لـ a نظير، لذا تأتي أولًا.

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

سؤال إضافي

افترض أن الكلمات يمكن أن تحتوي على أي أحرف Unicode بدلًا من 26 حرفًا صغيرًا. أي المفتاحين، الأحرف المرتبة أم أعداد الأحرف، يظل صالحًا، وما الذي ستغيّره فيه؟

تلميحات

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

فُتح 0 من 3

الحل

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

قارن كل كلمة بكل مجموعة

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

الفكرة

العلاقة بين الكلمات المكوّنة من الحروف نفسها متعدية: إذا كانت stone تطابق notes وكانت notes تطابق tones، فإن stone تطابق tones. لذلك لا تحتاج الكلمة الجديدة أبدًا إلى مطابقة كل فرد في المجموعة. تكفي مقارنتها بالكلمة الأولى في المجموعة لتحديد ما إذا كانت تنتمي إليها.

لمقارنة كلمتين، عُدَّ الحروف. تكون الكلمتان مكوّنتين من الحروف نفسها عندما يكون لهما الطول نفسه ويظهر كل حرف في إحداهما بالعدد نفسه الذي يظهر به في الأخرى. أضف 1 لكل حرف من الكلمة الأولى واطرح 1 لكل حرف من الكلمة الثانية، ثم تحقّق من أن العدادات الستة والعشرين كلها تنتهي عند 0.

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

تكمن الكلفة في المسح. عندما لا توجد كلمتان مكوّنتان من الحروف نفسها، تُقارَن كل كلمة بكل مجموعة تسبقها: 4000 كلمة تعني نحو 4000 × 3999 / 2 ≈ 8 × 10^6 مقارنات، تلامس كل منها ما يصل إلى 8 أحرف و26 عدّادًا. وهذا بطيء جدًا بالنسبة إلى Python وLua وR في أكبر الاختبارات، كما أن العمل ينمو بمربع طول القائمة، لذا ستتعثر أي لغة عند 10^5 كلمة.

الخوارزمية

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

def is_anagram(a, b):
    # Same length, and every letter appears as often in a as in b.
    if len(a) != len(b):
        return False
    counts = [0] * 26
    for c in a:
        counts[ord(c) - 97] += 1
    for c in b:
        counts[ord(c) - 97] -= 1
    return all(x == 0 for x in counts)


def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = []
    for word in sorted(strs):
        for group in groups:
            if is_anagram(group[0], word):
                group.append(word)
                break
        else:
            groups.append([word])
    return [" ".join(group) for group in groups]

التجميع حسب الأحرف المرتبة في خريطة تجزئة

الفكرة

بدلًا من السؤال عن المجموعة التي تنتمي إليها الكلمة، احسب اسم المجموعة من الكلمة نفسها. رتّب أحرف الكلمة، وستحصل جميع الكلمات المتخالفة الأحرف لها على النص نفسه: listen وsilent وenlist تصبح جميعها eilnst، بينما تصبح stone enost. تتشارك كلمتان الصيغة المرتّبة نفسها بالضبط عندما تحتويان على الأحرف نفسها، بالعدد نفسه من المرات، وهذا هو تعريف الكلمات المتخالفة الأحرف. لذا تُعدّ الصيغة المرتّبة مفتاحًا معياريًا للمجموعة.

بعد ذلك، تجمع خريطة تجزئة تربط المفاتيح بقوائم الكلمات كل شيء في مرور واحد. تتطلب كل كلمة عملية ترتيب واحدة لعدد لا يتجاوز 8 أحرف، وبحثًا واحدًا في الخريطة، ولا تُقارَن أبدًا بكلمة من مجموعة أخرى.

للحفاظ على الترتيب، رتّب المدخلات قبل التجميع، كما في النهج الأول. تصل الكلمات بالترتيب الأبجدي، لذا تمتلئ كل قائمة بالترتيب، ويدخل المفتاح إلى الخريطة عند وصول أول كلمة في مجموعته. تعيد الخرائط التي تحافظ على ترتيب الإدراج (قاموس Python، وMap في JavaScript، وLinkedHashMap في Java، وخريطة Dart، وتجزيئات Ruby، ومصفوفات PHP) المجموعات بذلك الترتيب. عندما لا يكون للخريطة ترتيب، خزّن فهرس كل مجموعة في الخريطة، وخزّن المجموعات نفسها في قائمة.

يتطلب ترتيب المدخلات نحو n log n مقارنةً لما يصل إلى k من الأحرف، أي نحو 5 × 10^4 مقارنة كلمات لـ 4000 كلمة بدلًا من 8 × 10^6. ويضيف إنشاء المفاتيح O(n · k log k)، وهو مقدار صغير مقارنةً بذلك لأن k ≤ 8.

الخوارزمية

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

def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = {}  # key (the letters in sorted order) -> the group's words
    for word in sorted(strs):
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    # A dict keeps insertion order, so the groups come out by first word.
    return [" ".join(words) for words in groups.values()]

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

التجميع هو الجزء الذي يتدرّب عليه الناس. تأتي معظم الإجابات الخاطئة في هذا الإصدار من ترتيب الناتج ومن المفاتيح غير الفريدة.

ترتيب المجموعات حسب مفتاحها بدلًا من كلمتها الأولى. المفتاح هو أصغر إعادة ترتيب لكلماتها، وليس إحدى تلك الكلمات: بالنسبة إلى ["cab", "bad"]، المفتاحان هما abc وabd، وهذا يجعل cab تأتي أولًا، لكن عند الترتيب حسب الكلمة الأولى، تأتي bad أولًا.
جمع الكلمات في مجموعة. يجب أن تعطي ["b", "a", "b"] الناتج b b؛ فالمجموعة تحتفظ بنسخة واحدة فقط.
إنشاء مفتاح من الأحرف المختلفة فقط. تستخدم ab وaabb الحرفين نفسيهما، لكن aabb تحتوي على حرفين من كل نوع، لذا فهما ليستا كلمتين مكوّنتين من الأحرف نفسها.
إنشاء مفتاح يجمع رموز الأحرف. لـ ad وbc المجموع نفسه، لذا فإن الجمع يدمج كلمات لا تشترك في أي حرف.
ترتيب كل مجموعة دون ترتيب المدخلات، ثم نسيان ترتيب المجموعات. عندئذٍ يصبح ترتيب الإدراج هو ترتيب المدخلات، لا ترتيب الكلمات الأولى.
ضمّ الكلمات يدويًا وترك مسافة في بداية سلسلة إحدى المجموعات أو نهايتها.

أسئلة شائعة4

ما هو التعقيد الزمني لمسألة تجميع الكلمات المتشابهة؟

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

هل مفتاح عدّ الأحرف أسرع من فرز كل كلمة؟

يستغرق مفتاح العدّ، أي كتابة أعداد مرات ظهور الأحرف الـ26 كنص مثل 1#0#2#…، زمنًا قدره O(k) بدلًا من O(k log k)، لذا يكون أفضل مع الكلمات الطويلة. أما مع الكلمات التي لا يتجاوز طولها 8 أحرف، فالفرز بالسرعة نفسها، ويكون الفرز الأبجدي للمخرجات أعلى كلفة من أيٍّ من المفتاحين. وكلا المفتاحين صحيح، لأن كلمتين لهما الأعداد نفسها بالضبط عندما تتطابق أحرفهما بعد الفرز.

لماذا لا نستخدم مجموع رموز الحروف كمفتاح؟

يمكن أن تُعطي أحرف مختلفة المجموع نفسه: فـ a + d يساوي b + c، لذا ستنتمي ad وbc إلى المجموعة نفسها. يجب أن يكون المفتاح متساويًا للكلمات المتطابقة الحروف ومختلفًا لكل ما عداها، وهذا ما تضمنه الأحرف المرتبة أو العدد الكامل لكل حرف. كما أن ضرب عدد أولي واحد لكل حرف دقيق أيضًا، لكن باستخدام 101 للحرف z، فإن كلمة تتكون من عشرة أحرف z تتجاوز بالفعل سعة عدد صحيح ذي 64 بت.

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

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

Python

def groupAnagrams(strs):
    # اكتب الكود هنا

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

الحالة 1

الحالة 2

الحالة 3

المدخلات

strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]

المتوقع

["apple", "enlist listen silent", "notes onset stone tones"]