Valid Anagram
تكون سلسلتان من المحارف متطابقتين في أحرفهما إذا كانت إحداهما إعادة ترتيب للأخرى: أي إنهما تستخدمان الأحرف نفسها، وبالعدد نفسه لكل حرف. لديك سلسلتان s وt مؤلفتان من أحرف إنجليزية صغيرة. أرجع true إذا كانت t إعادة ترتيب لأحرف s، وfalse خلاف ذلك.
الدالة
- sstring
- السلسلة النصية الأولى، أحرف صغيرة
- tstring
- السلسلة النصية التي ستختبر بها s
- تُرجعboolean
- صحيح إذا كان t يستخدم أحرف s نفسها تمامًا، كلًّا منها العدد نفسه من المرات
القيود
1 ≤ s.length, t.length ≤ 2 × 104sوtيحتويان على أحرف إنجليزية صغيرة فقط (aإلىz).- قد يختلف الطولان.
أمثلة
- المدخلات
- s = "listen"t = "silent"
- المخرجات
- true
- الشرح
- تحتوي كلتا الكلمتين على حرف واحد من كل من
eوiوlوnوsوt، لذا فإنsilentهيlistenبعد إعادة ترتيب حروفها.
- المدخلات
- s = "aabb"t = "abbb"
- المخرجات
- false
- الشرح
- الطولان متساويان، وكلاهما يستخدم الحرفين
aوbفقط، لكنaabbيحتوي على حرفَيa، بينما يحتويabbbعلى حرفaواحد. يجب أن تتطابق الأعداد، وليس الحروف فقط.
- المدخلات
- s = "cat"t = "cast"
- المخرجات
- false
- الشرح
- تتكوّن
castمن أربعة أحرف، وتتكوّنcatمن ثلاثة أحرف، لذا لا يمكن لأي إعادة ترتيب لـcatأن تكتبها.
+19 اختبارات مخفية عند الإرسال
سؤال إضافي
ماذا لو كان بإمكان السلاسل النصية أن تحتوي على أي محرف Unicode بدلًا من a إلى z؟ كيف ستغيّر طريقة العد؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
يتجاهل الجناس ترتيب الحروف. ما الذي يمكنك مقارنته بحيث يتجاهل الترتيب، لكنه يحتفظ بعدد مرات ظهور كل حرف؟
عند ترتيبهما حرفًا حرفًا، يصبح مقطعان متنافران الكلمةَ نفسها. والأسرع من ذلك: لا يوجد سوى 26 حرفًا، لذا يمكنك عدّ عدد مرات ظهور كل حرف.
إذا اختلف الطولان، فالإجابة هي
false. وإلا، احتفظ بـ 26 عدّادًا: أضف 1 لكل حرف منsواطرح 1 لكل حرف منt. تكون السلسلتان متشابهتين في ترتيب الحروف فقط عندما لا ينخفض أي عدّاد أبدًا إلى ما دون الصفر.
الحل
يحافظ الجناس الناقص على أعداد الأحرف ويتجاهل ترتيبها. لذا تحتاج إلى ملخّص لكل سلسلة نصية ينسى مواضع الأحرف، لكنه يتذكّر عدد مرات ظهور كل حرف. ينشئ الفرز هذا الملخّص في O(n log n)؛ وينشئه جدول يضم 26 عدّادًا في مرور واحد.
رتّب كلتا السلسلتين
الفكرة
يضع الفرز أحرف السلسلة بترتيب أبجدي ويمحو موضع بدء كل حرف. يُفرز listen إلى eilnst، وكذلك silent، لذا فهما كلمتان متطابقتان من حيث الحروف. تبقى aabb كما هي aabb، وتبقى abbb كما هي abbb؛ فهما تختلفان عند الفهرس 1، لذا فهما ليستا كذلك.
يعمل الاختبار في كلا الاتجاهين. إذا كانت t إعادة ترتيب لـ s، فإنهما تحتويان على الأحرف نفسها بالعدد نفسه، لذا ينتج الفرز التسلسل نفسه. وإذا تساوى التسلسلان بعد الفرز، فإن t تستخدم أحرف s نفسها تمامًا.
قارن الطولين أولًا: السلاسل ذات الأطوال المختلفة لا تكون متطابقة من حيث الحروف أبدًا، ويمكنك تخطي عمليتي الفرز. يستغرق الفرز زمنًا قدره O(n log n)، وتفرز معظم اللغات نسخة من الأحرف، ما يتطلب مساحة إضافية قدرها O(n). عند n = 2 × 10^4 تكون هذه الطريقة سريعة، لكن أسلوب العد يتطلب عملًا أقل.
الخوارزمية
- إذا اختلف طول
sوt، فأعِدfalse. - انسخ أحرف كل سلسلة إلى مصفوفة.
- رتّب كلتا المصفوفتين.
- أعِد
trueإذا كانت المصفوفتان المرتبتان متساويتين عنصرًا بعنصر.
def isAnagram(s, t):
if len(s) != len(t):
return False
return sorted(s) == sorted(t)عُدَّ كلَّ حرف
الفكرة
لا يمكن أن تظهر إلا 26 حرفًا، لذا احتفظ بعدّاد لكل حرف في مصفوفة من 26 خانة، مع الفهرس 0 للحرف a والفهرس 25 للحرف z. فهرس الحرف هو رمز محرفه مطروحًا منه رمز a. مرّ على s وزِد عدّاد كل حرف بمقدار 1، ثم مرّ على t وأنقصه بمقدار 1.
يمكنك التوقف مبكرًا: فالقيمة السالبة لعدّاد تعني أن t استخدم ذلك الحرف مرات أكثر مما استخدمه s. بالنسبة إلى aabb وabbb، تكون قيم العدّادات بعد المرور على s كالتالي: a: 2 وb: 2. ثم يأخذ t الحرف b ثلاث مرات، فتجعل المرة الثالثة قيمة b تساوي -1، وعندها تعيد false فورًا.
لماذا يكفي أن «لا يصبح أي عدّاد سالبًا»؟ الطولان متساويان، لذا يكون مجموع العدّادات 0 بعد المرور على السلسلتين. إذا لم تكن أي قيمة سالبة، فلن توجد قيمة موجبة يمكن موازنتها، لذا تكون جميع قيم العدّادات 0 وتتطابق التكرارات. لهذا يلزم التحقق من الطول، وليس مجرد اختصار.
تُقرأ كل سلسلة مرة واحدة، وهذا يستغرق زمنًا قدره O(n). تحتوي المصفوفة دائمًا على 26 رقمًا، مهما كان الطول، لذا تكون المساحة الإضافية O(1).
الخوارزمية
- إذا اختلف طول
sوt، فأعِدfalse. - أنشئ مصفوفة من 26 صفرًا.
- لكل حرف في
s، أضف 1 إلى عدّاده. - لكل حرف في
t، اطرح 1 من عدّاده؛ وإذا انخفض إلى ما دون 0، فأعِدfalse. - أعِد
true.
def isAnagram(s, t):
if len(s) != len(t):
return False
counts = [0] * 26 # counts[0] is 'a', counts[25] is 'z'
for ch in s:
counts[ord(ch) - ord("a")] += 1
for ch in t:
index = ord(ch) - ord("a")
counts[index] -= 1
if counts[index] < 0:
return False # t uses this letter more often than s
return True
أخطاء شائعة وحالات حدّية
تنتج معظم الإجابات الخاطئة عن التحقق من الحروف التي تظهر بدلًا من عدد مرات ظهورها، أو عن إغفال التحقق من الطول.
- مقارنة مجموعات الحروف. يستخدم كلٌّ من
aabbوabbbالحرفينaوbفقط، ومع ذلك فهما ليسا متغايرَي الأحرف. - التحقق من أن كل حرف في
tيظهر في موضع ما فيsمن دون شطبه. يجتازaabوabbهذا الاختبار في كلا الاتجاهين. - تجاوز التحقق من الطول في طريقة العد. مع
s = abوt = a، لا ينخفض أي عدّاد عن 0، لذا سيُرجع الكودtrueعلى نحو خاطئ. - فهرسة مصفوفة العد باستخدام رمز الحرف الخام. قيمة
aهي 97، وهي أبعد بكثير من نهاية مصفوفة طولها 26؛ اطرح رمزaأولًا. في Lua وR، أضف 1 لأن الفهرسة في مصفوفاتهما تبدأ من 1.
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة التحقق من كون كلمتين متضادتَي الأحرف؟
يستغرق عدّ الأحرف زمنًا O(n) ومساحة إضافية O(1)، لأن مصفوفة العداد تحتوي على 26 خانة بغض النظر عن طول السلاسل النصية. يستغرق ترتيب السلسلتين زمنًا O(n log n)، ويستهلك عادةً مساحة O(n) للنسخ المرتبة.
هل الأفضل الفرز أم العدّ عند التحقق مما إذا كانت كلمتان من أحرف إحداهما الأخرى؟
يكون العد أسرع نظريًا، O(n) مقارنةً بـ O(n log n)، ويمكنه التوقف بمجرد الإفراط في استخدام أحد الأحرف. كتابة الفرز أقصر، ويعمل مع أي أبجدية دون تغييرات. في مقابلة، اذكر الفرز أولًا، ثم حسّنه باستخدام العد.
كيف تتحقق من كون كلمتين متقاربتين متطابقتين في الحروف وتحتويان على أحرف Unicode؟
استبدل مصفوفة العدّادات الـ26 بخريطة تجزئة تربط كل حرف بعدد مرات ظهوره. أضف 1 لكل حرف في s، واطرح 1 لكل حرف في t، وتحقّق من أن قيمة كل عدّاد تنتهي عند 0. اقرأ السلاسل حرفًا حرفًا، لا بايتًا بايتًا، حتى يُحتسب الحرف المخزّن في عدة بايتات مرة واحدة.
لماذا نستخدم مصفوفة عدّاد واحدة بدلًا من اثنتين؟
تعمل مصفوفتان، واحدة لكل سلسلة نصية، أيضًا: عُدَّ أحرف كل سلسلة نصية، ثم قارن المصفوفتين. تستخدم مصفوفة واحدة تزداد مع s وتنقص مع t نصف الذاكرة، وتتيح لك إرجاع false فور أن يصبح أحد العدّادات سالبًا، من دون حلقة مقارنة نهائية.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def isAnagram(s, t):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
s = "listen" t = "silent"
المتوقع
true