Group Anagrams

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

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

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

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

متوسطالتجزئة الترتيب

+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 فلا يطابق أي شيء، وباعتباره الكلمة الأولى، يتصدر.

المدخلات: 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، لذا تأتي أولًا.

سؤال إضافي

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

تلميحات

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

فُتح 0 من 3

الحل

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

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

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

الفكرة

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

عندما لا توجد كلمتان متناقلتا الأحرف، تُقارَن كل كلمة بكل مجموعة تسبقها: 4000 كلمة تُجري نحو 8 × 10^6 مقارنة، تمس كل منها ما يصل إلى 8 أحرف و26 عدّادًا.

الخوارزمية

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

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. تتشارك كلمتان الصيغة المرتبة نفسها بالضبط عندما تحتويان على الحروف نفسها بالعدد نفسه، وهذا هو تعريف المفردات المتخالفة. عندئذٍ، تجمع خريطة تجزئة تربط المفتاح بقائمة كلمات كل العناصر في مرور واحد، ولا تُقارَن أي كلمة بكلمات مجموعة أخرى.

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

يستغرق فرز المدخلات نحو 5 × 10^4 مقارنة بين الكلمات لـ 4000 كلمة، بدلًا من 8 × 10^6.

الخوارزمية

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

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 الحرفين نفسيهما، لكنهما ليسا كلمتين متطابقتين عند إعادة ترتيب الأحرف.
ترتيب كل مجموعة دون ترتيب المدخلات، ودون ترتيب المجموعات. عندئذٍ يتبع ترتيب الإدراج ترتيب المدخلات، لا ترتيب الكلمات الأولى.

أسئلة شائعة3

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

يتطلب إنشاء المفاتيح ذات الأحرف المرتبة 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 بت.

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

اختبار #1

اختبار #2

اختبار #3

وسيط

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

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

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