Alien Dictionary
تُرتَّب قائمة من الكلمات وفق أبجدية لا تعرفها: الأحرف الإنجليزية الصغيرة الـ 26 بترتيب سري ما. تُقارَن الكلمات بالطريقة المعتادة. يحدد أول موضع تختلف فيه كلمتان أيَّ الحرفين يأتي أولًا في الأبجدية، وإذا كانت إحدى الكلمتين بدايةً للأخرى، فتأتي الكلمة الأقصر أولًا.
أعِد الأحرف التي تظهر في الكلمات، في سلسلة واحدة مرتبة أبجديًا. إذا كانت هناك عدة ترتيبات تلائم القائمة، فأعِد الترتيب الذي يأتي أولًا وفق الترتيب القاموسي المعتاد. إذا لم يلائم القائمة أي ترتيب، فأعِد "invalid".
الدالة
- wordsstring-array
- الكلمات، مرتبة حسب الأبجدية المجهولة
- تُرجعstring
- الأحرف بأصغر ترتيب يناسب، أو "invalid"
القيود
1 ≤ words.length ≤ 50001 ≤ words[i].length ≤ 10- تتكوّن كل كلمة من أحرف إنجليزية صغيرة فقط.
- قد تظهر الكلمة نفسها أكثر من مرة.
أمثلة
- المدخلات
- words = ["tea", "ten", "ate", "act", "cat"]
- المخرجات
- "etacn"
- الشرح
- يختلف
teaوtenأولًا عند a وn، لذا يأتي a قبل n. وتُبيّن الأزواج الأخرى أن t يأتي قبل a، وt قبل c، وa قبل c. لا توجد قاعدة تذكر e، لذا يضعه الترتيب الأصغر أولًا، ثم t، ثم a، ثم c وn، إذ لا قيود عليهما عندئذ، مع وضع c أولًا.
- المدخلات
- words = ["bat", "tab", "tub", "bus"]
- المخرجات
- "invalid"
- الشرح
batقبلtabيضع b قبل t، وtabقبلtubيضع a قبل u، وtubقبلbusيضع t قبل b. لا يمكن أن يكون كلٌّ من b قبل t وt قبل b صحيحًا، لذا لا يوجد ترتيب مناسب.
- المدخلات
- words = ["cooking", "cook"]
- المخرجات
- "invalid"
- الشرح
cookهي بدايةcooking، لذا تأتي أولًا في كل أبجدية. تضعها القائمة في المرتبة الثانية، وهو ما لا يمكن تفسيره بأي ترتيب للحروف.
+20 اختبارات مخفية عند الإرسال
سؤال إضافي
كيف يمكنك معرفة ما إذا كان ترتيب الملاءمة هو الترتيب الوحيد؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
انظر إلى كلمتين متجاورتين، مثل
teaوten. ماذا تخبرك هاتان الكلمتان عن الأبجدية، وما الذي تتركانه دون حسم؟يعطي كل زوج متجاور قاعدة واحدة على الأكثر: عند أول موضع تختلف فيه الكلمتان، يأتي حرف الكلمة الأولى قبل حرف الكلمة الثانية. القواعد هي حواف رسم بياني للحروف، والإجابة هي ترتيب يحترم كل حافة. انتبه إلى زوج لا يوجد فيه موضع اختلاف وتكون فيه الكلمة الأولى أطول.
استخدم خوارزمية كان: ضع حرفًا لا تشير إليه أي قاعدة، واحذف قواعده، ثم كرر ذلك. احتفظ بالحروف الجاهزة في كومة صغرى، وضع دائمًا الحرف الأصغر. إذا بقيت بعض الحروف دون وضع، فالقواعد تحتوي على دورة.
الحل
تُخفي القائمة ترتيبها الأبجدي في المواضع التي تختلف فيها الكلمات المتجاورة لأول مرة. ويعطي كل موضع من هذه المواضع قاعدةً واحدة: الحرف x يسبق الحرف y، وتشكّل القواعد رسمًا بيانيًا موجّهًا للأحرف. والترتيب المناسب هو ترتيب طوبولوجي لذلك الرسم البياني. وهناك أمران يجعلان القائمة مستحيلة: وجود دورة بين القواعد، ووضع كلمة قبل بادئتها نفسها. إن اختيار أصغر حرف متاح في كل خطوة باستخدام كومة صغرى يعطي أصغر ترتيب مناسب.
جرّب كل ترتيب للحروف
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
الإجابة هي ترتيب ما للأحرف المميّزة وعددها k. يمكنك اختبار ترتيب واحد مباشرةً: تكون القائمة مرتّبة وفقه إذا كان كل زوج من الكلمات المتجاورة مرتّبًا بحسبه. قارن الكلمتين عند أول موضع تختلفان فيه؛ يجب أن يأتي حرف الكلمة الأولى قبل حرف الكلمة الثانية في الترتيب. وإذا لم تختلفا أبدًا، فيجب ألا تكون الكلمة الأولى أطول. تكفي مقارنة الكلمات المتجاورة، لأن الترتيب يشكّل سلسلة: إذا كانت كل كلمة لا تتجاوز التالية، فالقائمة كلها مرتّبة.
والآن استعرض الترتيبات من الأصغر إلى الأكبر. ابدأ بالأحرف حسب الترتيب الأبجدي، وهو أصغر ترتيب على الإطلاق، وانتقل في كل مرة إلى الترتيب الأكبر التالي (التبديل التالي). أول ترتيب يجتاز الاختبار هو أصغر ترتيب يفي بالغرض. إذا لم يجتز أي ترتيب الاختبار، فأعِد "invalid".
هذا صحيح، لكنه غير عملي مع مدخلات حقيقية. للأحرف k عدد k! من الترتيبات: 5 أحرف تعطي 120، و10 أحرف تعطي 3,628,800، أما الأحرف الـ26 كلها فتعطي نحو 4 × 10^26. يقرأ كل اختبار القائمة كاملة، أي C حرفًا إجمالًا، وقد يصل العدد إلى 5 × 10^4. في الاختبارات الكبيرة يبدأ أصغر ترتيب يفي بالغرض بالحرف f أو z، لذا يسبقه عدد هائل فلكيًا من الترتيبات، وعندما لا يكون هناك ترتيب مناسب، يجب أن يجرّب البحث جميع الترتيبات.
الخوارزمية
- اجمع الأحرف المميّزة ورتّبها أبجديًا.
- سجّل موضع كل حرف (رتبته) في الترتيب الحالي.
- تحقّق من كل زوج متجاور: عند أول موضع يختلف فيه الحرفان، يجب أن يكون ترتيب حرف الكلمة الأولى أصغر؛ وإذا لم يوجد موضع مختلف، فيجب ألا تكون الكلمة الأولى أطول.
- إذا اجتاز كل زوج الاختبار، فأعِد الترتيب. وإلا فانتقل إلى الترتيب الأكبر التالي.
- عندما لا يوجد ترتيب تالٍ، فأعِد
"invalid".
from itertools import permutations
def fits(words, rank):
# The list is sorted under rank when every neighbouring pair is in order.
for first, second in zip(words, words[1:]):
for x, y in zip(first, second):
if x != y:
if rank[x] > rank[y]:
return False
break
else:
# One word starts the other: the shorter must come first.
if len(first) > len(second):
return False
return True
def alienOrder(words):
letters = sorted(set("".join(words)))
# permutations() of a sorted list yields the orders from smallest to largest,
# so the first order that fits is the answer.
for order in permutations(letters):
rank = {ch: i for i, ch in enumerate(order)}
if fits(words, rank):
return "".join(order)
return "invalid"خوارزمية كان باستخدام كومة صغرى
الفكرة
استخرج القواعد من القائمة بدلًا من تخمين الترتيب. خذ كلمتين متجاورتين وابحث عن أول موضع تختلفان فيه. تتفق tea وten في الحرفين t وe وتختلفان عند a وn، لذا يأتي a قبل n. هذه هي القاعدة الوحيدة التي نستخلصها من الزوج. الأحرف بعد أول اختلاف لا تخبرنا بشيء: تأتي act قبل cat لأن a يأتي قبل c، ولا تُقارَن أبدًا الأحرف c وt التي تلي ذلك في act بالحرفين a وt في cat. لذا يعطي كل زوج قاعدة واحدة على الأكثر، أي حافة من حرف إلى آخر.
الزوج الذي لا يحتوي على موضع اختلاف هو فخ البادئة. إحدى الكلمتين هي بداية الأخرى، ويجب أن تأتي الكلمة الأقصر أولًا في أي أبجدية. لا مشكلة في أن تأتي cook قبل cooking، فهذا لا يعطي أي قاعدة. أما إذا جاءت cooking قبل cook، فلا يمكن ترتيب الكلمات مطلقًا، لذا أرجِع "invalid" فورًا. الحلقة التي تبحث عن الأحرف المختلفة فقط لن تجد شيئًا في هذا الزوج، وستتابع عملها ثم تُرجع ترتيبًا لقائمة لا يمكن لأي أبجدية أن تنتجها.
تحتاج الآن إلى ترتيب للأحرف يحترم كل الحواف، أي ترتيب طوبولوجي. تبني خوارزمية Kahn واحدًا. احسب عدد الحواف المتجهة إلى كل حرف (درجة دخوله)، وضع حرفًا عدده 0، واحذف حوافه الصادرة، ثم كرر ذلك. يظل الحرف الواقع على دورة مرتبطًا دائمًا بحافة من الحرف الذي يسبقه في الدورة، لذا لا يصل عدده أبدًا إلى 0 ولا يُوضَع أبدًا. إذا كان عدد الأحرف الموضوعة أقل من عدد الأحرف الواردة في الكلمات، فهناك دورة، وتكون الإجابة "invalid".
للحصول على أصغر ترتيب، احتفظ بالأحرف التي عددها 0 في كومة دنيا، وضع الأصغر دائمًا. هذا الاختيار الجشع آمن. فالحرف الأول في أي ترتيب يفي بالشروط يكون عدده 0، لذا فإن أصغر حرف جاهز هو أصغر حرف ممكن في الموضع الأول. وضعه يحذف الحواف ولا يمنع أي حرف آخر من الترتيب: فكل حرف كان جاهزًا يظل جاهزًا. وينطبق المنطق نفسه بعد ذلك على الموضع الثاني، وهكذا. في المثال الأول، يكون كل من e وt جاهزًا في البداية، ويأتي e أولًا. ستُنتج قائمة الانتظار العادية ترتيبًا صالحًا أيضًا، لكنه ليس الأصغر دائمًا.
التكلفة هي المرور على القائمة مرة واحدة، التي تضم C حرفًا إجمالًا، للعثور على الاختلافات الأولى. ومع k ≤ 26 حرفًا، يوجد على الأكثر k² حافة، تُحفظ في جدول حجمه k في k بحيث تُخزَّن القاعدة المكررة مرة واحدة، ولا تحتوي الكومة أبدًا على أكثر من k حرفًا. لذا فالتعقيد الزمني هو O(C + k²)، وتستغرق العملية بضعة أجزاء من الألف من الثانية في أكبر الاختبارات.
الخوارزمية
- حدّد كل حرف يظهر في الكلمات.
- لكل زوج من الكلمات المتجاورة، أوجد أول موضع يختلفان فيه. إذا وُجد، فأضف الحافة من حرف الكلمة الأولى إلى حرف الكلمة الثانية مرة واحدة. وإذا لم يوجد وكان طول الكلمة الأولى أكبر، فأعِد
"invalid". - احسب عدد الحواف الداخلة لكل حرف، وأضف كل حرف يظهر وعدده 0 إلى كومة صغرى.
- أخرج أصغر حرف وألحِقه. أنقص عدد كل حرف يشير إليه، وأضف إلى الكومة أي حرف يصل عدده إلى 0.
- إذا كان عدد الحروف التي أُدرجت أقل من عدد الحروف الظاهرة، فأعِد
"invalid". وإلا فأعِد الحروف المُدرجة.
import heapq
def alienOrder(words):
# Letters are numbered 0 for 'a' up to 25 for 'z'.
present = [False] * 26
for word in words:
for ch in word:
present[ord(ch) - 97] = True
# before[a][b] is True once you know letter a comes before letter b.
before = [[False] * 26 for _ in range(26)]
indegree = [0] * 26
for first, second in zip(words, words[1:]):
for x, y in zip(first, second):
if x != y:
# Only the first difference tells you anything.
a, b = ord(x) - 97, ord(y) - 97
if not before[a][b]:
before[a][b] = True
indegree[b] += 1
break
else:
# No difference: one word starts the other, so the shorter must come first.
if len(first) > len(second):
return "invalid"
# A min-heap of the letters with nothing left before them.
heap = [c for c in range(26) if present[c] and indegree[c] == 0]
heapq.heapify(heap)
order = []
while heap:
c = heapq.heappop(heap)
order.append(chr(c + 97))
for nxt in range(26):
if before[c][nxt]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
heapq.heappush(heap, nxt)
# A letter on a cycle never gets down to indegree 0, so it is never placed.
if len(order) < sum(present):
return "invalid"
return "".join(order)
أخطاء شائعة وحالات حدّية
معظم الإجابات الخاطئة هنا لا تكون واضحة: فقراءة القاعدة على نحو خاطئ تظل تنتج ترتيبًا ما، لكنه يكون الترتيب الخاطئ.
- أخذ أكثر من قاعدة من زوج واحد. الموضع الأول المختلف فقط هو المهم.
actقبلcatيعني أن a تسبق c، ولا يقول شيئًا عن الحروف التي تليها. - إغفال حالة البادئة. في
cookingقبلcookلا يوجد حرف مختلف، لذا فإن الحلقة التي تتعامل مع الاختلافات فقط لن ترى شيئًا، وستعيد ترتيبًا. الإجابة هي"invalid". - إغفال الحروف التي لا تظهر في أي قاعدة. في المثال الأول، لا تذكر أي قاعدة الحرف e، ومع ذلك يجب أن يكون ضمن الإجابة، والترتيب الأصغر يضعه أولًا.
- استخدام طابور عادي بدلًا من كومة صغرى. تعيد خوارزمية Kahn باستخدام طابور ترتيبًا صالحًا، لكن المطلوب هو أصغر ترتيب.
- احتساب قاعدة مكررة مرتين في درجة الدخول، مع تخزينها مرة واحدة في الرسم البياني. عندها لا يصل الحرف إلى 0 أبدًا، ويُبلّغ عن قائمة صالحة على أنها دورة. خزّن كل قاعدة مرة واحدة، أو أضفها واحذفها العدد نفسه من المرات.
- اعتبار كلمتين متجاورتين متطابقتين حالة بادئة. تكون الكلمة التي تليها الكلمة نفسها مرتبة؛ وحده وجود كلمة أطول قبل بادئتها نفسها يجعل الترتيب مستحيلًا.
أسئلة شائعة4
ما هو التعقيد الزمني لقاموس الفضائيين؟
O(C + k²)، حيث C هو العدد الإجمالي للأحرف في الكلمات وk ≤ 26 هو عدد الأحرف المختلفة. تعثر عملية مرور واحدة على القائمة على أول اختلاف في كل زوج من الكلمات المتجاورة، وتزور خوارزمية Kahn ما يصل إلى k² حافة. تضيف الكومة الدنيا O(k log k)، وهو مقدار ضئيل مقارنةً بالباقي. يشغل جدول الحواف مساحة O(k²).
لماذا نقارن الكلمات المتجاورة فقط؟
الترتيب خاصية متعدية: إذا كانت كل كلمة لا تتجاوز الكلمة التي تليها، فالقائمة بأكملها مرتبة. لذا فإن أي قاعدة يمكن استنتاجها من كلمتين متباعدتين تكون متحققة بالفعل بفضل الأزواج المتجاورة بينهما. مقارنة كل زوج من الكلمات لا تضيف أي معلومات، وتكلّف O(n²) مقارنة بدلًا من n-1.
لماذا يؤدي اختيار أصغر حرف جاهز إلى الحصول على أصغر ترتيب؟
يجب أن يبدأ أي ترتيب مطابق بحرف لا تشير إليه أي قاعدة. لذلك يكون أصغر حرف من هذا النوع هو أصغر حرف أول ممكن، ووضعه لا يؤدي إلا إلى إزالة الحواف، لذا يظل كل حرف آخر جاهز متاحًا. يؤدي تكرار هذا الاستدلال في كل موضع إلى بناء أصغر ترتيب حرفًا تلو الآخر. وتمنحك الكومة الصغرى أصغر حرف جاهز في O(log k).
لماذا تكون الكلمة التي تسبق بادئتها غير صالحة؟
في كل أبجدية، تأتي الكلمة بعد بادئتها، لأن المقارنة تنفد من الحروف في الكلمة الأقصر قبل أن تجد اختلافًا. لذا فإن cooking قبل cook يعني أن الترتيب غير صحيح مهما كانت الحروف، ولا يمكن لأي قاعدة إصلاح ذلك. وهذه هي الطريقة الوحيدة التي يمكن بها أن تكون القائمة مستحيلة من دون وجود دورة بين قواعدها.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def alienOrder(words):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
words = ["tea", "ten", "ate", "act", "cat"]
المتوقع
"etacn"