Palindrome String
تكون السلسلة النصية متناظرة عندما تُقرأ بالطريقة نفسها من اليسار إلى اليمين ومن اليمين إلى اليسار، مثل level. اكتب دالة تستقبل سلسلة نصية s مكوّنة من أحرف إنجليزية صغيرة، وتُرجع true إذا كانت s متناظرة وfalse خلاف ذلك.
الدالة
- sstring
- السلسلة النصية بأحرف صغيرة المراد التحقق منها
- تُرجعboolean
- صحيح عندما تُقرأ s بالطريقة نفسها في كلا الاتجاهين
القيود
1 ≤ s.length ≤ 5 × 104sيحتوي على أحرف إنجليزية صغيرة فقط (aإلىz).
أمثلة
- المدخلات
- s = "racecar"
- المخرجات
- true
- الشرح
- قارن من الخارج إلى الداخل:
rمعr، وaمعa، وcمعc. الحرف الأوسطeليس له مقابل ولا يحتاج إلى مقابل، لذا الإجابة هيtrue.
- المدخلات
- s = "abba"
- المخرجات
- true
- الشرح
- عندما يكون الطول زوجيًا، يكون لكل حرف نظير: يتطابق حرفا
aويتطابق حرفاb، لذا تكون الإجابةtrue.
- المدخلات
- s = "coddy"
- المخرجات
- false
- الشرح
- الحرف الأول
cوالحرف الأخيرyمختلفان بالفعل، لذا فإنcoddyليست متناظرة، والإجابة هيfalse.
+16 اختبارات مخفية عند الإرسال
سؤال إضافي
تُعدّ جملة مثل Was it a car or a cat I saw متناظرة إذا تجاهلت حالة الأحرف والمسافات وعلامات الترقيم. كيف ستغيّر المؤشرين لتجاوز هذه الأحرف؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
إذا كان
sمتناظرًا، فأيّ حرف يجب أن يساويه حرفه الأول؟يجب أن يكون الحرف عند الفهرس
iمساويًا للحرف عند الفهرسn-1-i. يكفي التحقق من كل زوج من هذه الأزواج مرة واحدة فقط، لذا يكفي فحص نصف الفهارس.ضع فهرسًا واحدًا في البداية وآخر في النهاية. قارن الحرفين، وأعِد
falseعند عدم التطابق، وحرّك كلا الفهرسين خطوة واحدة إلى الداخل حتى يلتقيا.
الحل
تكون الكلمة المتناظرة مساوية لنظيرها المعكوس، لذا ينشئ الفحص المباشر النسخة المعكوسة ويقارن بينهما. أما الفحص الأفضل فلا ينشئ شيئًا: يجب أن يتطابق الحرف الأول مع الأخير، والثاني مع ما قبل الأخير، وهكذا باتجاه المنتصف. يختبر فهرسان يتحركان إلى الداخل هذه الأزواج في مواضعها، ويتوقفان عند أول اختلاف.
قارن السلسلة بنسختها المعكوسة
الفكرة
قراءة s بالطريقة نفسها في الاتجاهين تعني أن s تساوي معكوسها. لذا اعكسها وقارن: معكوس racecar هو racecar، ومعكوس coddy هو yddoc، وهو مختلف.
إنشاء المعكوس والمقارنة بينهما يلمس كل حرف مرة واحدة، لذا فالزمن هو O(n). وتحتفظ النسخة المعكوسة بـ n أحرف إضافية، أي مساحة إضافية مقدارها O(n): عند n = 5 × 10^4، يعني ذلك إنشاء 50,000 حرف لمجرد مقارنتها والتخلص منها.
كما أنه ينفّذ العمل كاملًا في كل مرة. يُحسم أمر coddy من حرفيه الأول والأخير، ومع ذلك يعكس هذا الأسلوب الأحرف الخمسة كلها قبل أن يفحصها.
الخوارزمية
- أنشئ معكوس
sباستخدام دالة العكس في اللغة أو حلقة تبدأ من الحرف الأخير وصولًا إلى الحرف الأول. - قارن المعكوس بـ
s. - أعد
trueإذا كانا متساويين، وfalseخلاف ذلك.
def isPalindrome(s):
return s == s[::-1]مؤشران من الطرفين
الفكرة
ينقل العكس الحرف عند الفهرس i إلى الفهرس n-1-i، لذا تكون s مساوية لعكسها تمامًا عندما تكون s[i] مساوية لـ s[n-1-i] لكل i. يظهر كل زوج مرتين في تلك القائمة، لذا افحص النصف الأيسر فقط. ضع left عند الفهرس 0 وright عند الفهرس n-1، وقارن الحرفين، ثم حرّك كلا المؤشرين خطوة واحدة إلى الداخل.
توقّف عندما يلتقي المؤشران أو يتجاوز أحدهما الآخر. في racecar يفحصان أزواج الفهارس (0, 6) و(1, 5) و(2, 4)، ثم يلتقيان عند الفهرس 3، حيث يوجد الحرف الأوسط e الذي لا يحتاج إلى حرف يقابله. في abba يفحصان (0, 3) و(1, 2) ثم يتجاوز أحدهما الآخر. يثبت أول زوج مختلف أن الإجابة هي false، لذا أعد النتيجة فورًا: يُحسم أمر coddy بعد مقارنة واحدة.
يحدث ما لا يزيد عن n / 2 من المقارنات، وهذا يعني زمنًا قدره O(n)، والذاكرة الوحيدة المستخدمة هي فهرسان، أي مساحة O(1). أما R فهي الاستثناء: إذ تقرأ السلسلة أولًا على هيئة متجه من رموز الأحرف، ما يكلّف O(n).
الخوارزمية
- عيّن
left = 0وright = n-1. - ما دام
left < right، قارنs[left]معs[right]. - إذا اختلفا، فأعِد
false. - وإلا، أضف 1 إلى
left، واطرح 1 منright، وكرّر. - عندما يلتقي المؤشران أو يتجاوز أحدهما الآخر، تكون كل الأزواج قد تطابقت: أعِد
true.
def isPalindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
أخطاء شائعة وحالات حدّية
الحلقة قصيرة، لذا تكمن الأخطاء في حدودها وعبارات الإرجاع فيها.
- إرجاع
trueبمجرد تطابق زوج واحد. تمرabcaعبر الزوج الخارجي وتفشل عند الزوج الداخلي، لذا لا يجوز إرجاعtrueإلا بعد انتهاء الحلقة. - بدء
rightعندnبدلًا منn-1، ما يؤدي إلى القراءة بعد نهاية السلسلة (في C، بعد المحرف المنهي'\0'). في Lua وR، تبدأ الفهارس من1وتنتهي عندn، لذا يبدأrightهناك عندn. - مقارنة السلاسل بحسب العنوان. في C، تقارن
reversed == sمؤشّرين، وتكون النتيجة دائمًا false عند استخدام نسخة جديدة؛ استخدمstrcmp. - إنشاء السلسلة المعكوسة باستخدام
result = result + chداخل حلقة. تنسخ كل خطوة السلسلة كاملة حتى تلك اللحظة، ما يعني نسخ نحو1.25 × 10^9محرفًا عند التعامل مع 50,000 حرف. - فهرسة سلسلة Swift باستخدام عدد صحيح. لن يُترجم ذلك بنجاح؛ تجوّل عبر
s.utf8باستخدام فهارسها الخاصة، أو انسخ المحارف إلى مصفوفة.
أسئلة شائعة4
كيف تتحقق مما إذا كانت السلسلة النصية متناظرة؟
قارن الحرف الأول بالأخير، والثاني بما قبل الأخير، وهكذا باتجاه الوسط. إذا اختلف أي زوج، فالسلسلة ليست متناظرة؛ وإذا تطابق كل زوج، فهي كذلك. ينفّذ فهرسان يبدآن من الطرفين ويتحركان نحو الداخل ذلك في مرور واحد.
هل يمكنك التحقق مما إذا كانت سلسلة نصية متناظرة دون استخدام ذاكرة إضافية؟
نعم. يفحص التحقق باستخدام مؤشّرين الأحرف في مواضعها ويخزّن فهرسين فقط، لذا يستخدم مساحة إضافية O(1). مقارنة s بنسختها المعكوسة أقصر في الكتابة، لكنها تنشئ سلسلة ثانية مكوّنة من n حرفًا.
ما هو التعقيد الزمني للتحقق مما إذا كانت السلسلة النصية متناظرة؟
تعقيده O(n) لسلسلة طولها n. يُجري فحص المؤشرين مقارنات لا تتجاوز n / 2، ويتوقف عند أول اختلاف؛ لذا يُحسم الأمر بعد مقارنة واحدة إذا اختلف الحرفان الأول والأخير في السلسلة.
هل الحرف الواحد متناظر؟
نعم. يُقرأ الحرف نفسه في كلا الاتجاهين، لذا فالإجابة هي true. في حلقة المؤشرين، يبدأ كلٌّ من left وright عند الفهرس 0، ولا تُنفَّذ الحلقة مطلقًا، وتُرجع الدالة true.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def isPalindrome(s):
# اكتب الشيفرة هناالحالة 1
الحالة 2
الحالة 3
المدخلات
s = "racecar"
المتوقع
true