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.
سؤال إضافي
كيف ستغيّر المؤشرين لتجاوز المسافات وعلامات الترقيم وتجاهل حالة الأحرف، بحيث تُعدّ Was it a car or a cat I saw متناظرة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
إذا كان
sمتناظرًا، فأيّ حرف يجب أن يكون الحرف الأول فيه مساويًا له؟يجب أن يكون الحرف عند الفهرس
iمساويًا للحرف عند الفهرسn-1-i. يكفي التحقق من كل زوج من هذا النوع مرة واحدة، لذا يكفي استخدام نصف الفهارس.ضع فهرسًا واحدًا في البداية وآخر في النهاية. قارن الحرفين، وأعِد
falseعند عدم التطابق، وحرّك كلا الفهرسين خطوة واحدة إلى الداخل حتى يلتقيا.
الحل
الكلمة أو العبارة المتناظرة تقرأ بالطريقة نفسها عند عكسها، لذا يمكنك إنشاء النسخة المعكوسة ومقارنتها. لا تحتاج إلى إنشاء نسخة: يجب أن يتطابق الحرف الأول مع الأخير، والثاني مع ما قبل الأخير، وهكذا. يختبر مؤشّران يتحركان نحو الداخل هذه الأزواج في مواضعها، ويتوقفان عند أول اختلاف.
قارن السلسلة بنسختها المعكوسة
الفكرة
اعكس s وقارن: عند عكس racecar تصبح racecar، وعند عكس coddy تصبح yddoc. تكون السلسلة النصية متماثلة عند قراءتها في الاتجاهين بالضبط عندما تساوي معكوسها.
التعقيد الزمني هو O(n)، لكن النسخة المعكوسة تستهلك مساحة إضافية قدرها O(n)، أي 50,000 محرف عند n = 5 × 10^4. والعمل أيضًا كامل دائمًا: يُحسم أمر coddy من خلال حرفيه الأول والأخير، ومع ذلك تُعكس الأحرف الخمسة كلها أولًا.
الخوارزمية
- أنشئ معكوس
sباستخدام دالة العكس في اللغة أو حلقة تبدأ من الحرف الأخير حتى الحرف الأول. - قارن المعكوس مع
s. - أعِد
trueإذا كانا متساويين وfalseخلاف ذلك.
def isPalindrome(s):
return s == s[::-1]مؤشران من كلا الطرفين
الفكرة
يؤدي عكس الترتيب إلى نقل الفهرس i إلى الفهرس n-1-i، لذا تكون s مساويةً لمعكوسها تمامًا عندما تكون s[i] مساويةً لـ s[n-1-i] لكل i. يظهر كل زوج مرتين في هذا الشرط، لذا يكفي التحقق من النصف الأيسر. في racecar، الأزواج هي (0, 6) و(1, 5) و(2, 4)؛ ولا يحتاج الحرف الأوسط e عند الفهرس 3 إلى شريك.
أول زوج مختلف يثبت أن الإجابة هي 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بين مؤشّرين، وتكون النتيجة خاطئة عند استخدام نسخة؛ استخدمstrcmp. - إنشاء السلسلة المعكوسة باستخدام
result = result + ch. تنسخ كل خطوة السلسلة التي تكوّنت حتى تلك اللحظة: نحو1.25 × 10^9عملية نسخ للمحارف عند التعامل مع 50,000 حرف. - فهرسة سلسلة Swift باستخدام عدد صحيح: لن يُترجم ذلك. مرّر على
s.utf8أو انسخ المحارف إلى مصفوفة.
أسئلة شائعة4
كيف تتحقق مما إذا كانت السلسلة النصية متناظرة؟
قارن الحرف الأول بالأخير، والثاني بما قبل الأخير، وهكذا باتجاه المنتصف. إذا اختلف أي زوج، فالسلسلة ليست متناظرة. يُنجز فهرسان يبدأان من الطرفين ويتحركان نحو الداخل ذلك في مرور واحد.
هل يمكنك التحقق مما إذا كانت سلسلة نصية متناظرة دون استخدام ذاكرة إضافية؟
نعم. يفحص التحقق باستخدام مؤشرين الأحرف في مواضعها ويخزّن فهرسين، لذا يستخدم مساحة إضافية O(1). مقارنة s بنسختها المعكوسة أقصر في الكتابة، لكنها تنشئ سلسلة ثانية مكوّنة من n أحرف.
ما هو التعقيد الزمني للتحقق مما إذا كانت سلسلة نصية متناظرة؟
O(n) لسلسلة نصية طولها n. يجري فحص المؤشرين n / 2 مقارنةً على الأكثر، ويتوقف عند أول اختلاف، لذا يتطلب coddy مقارنةً واحدة.
هل يُعدّ الحرف الواحد متناظرًا؟
نعم، تُقرأ بالطريقة نفسها في كلا الاتجاهين. في حلقة المؤشرين left وright، يبدأ كلاهما عند الفهرس 0، ولا تُنفَّذ الحلقة أبدًا، وتُرجع الدالة true.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def isPalindrome(s):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
s = "racecar"
الإخراج المتوقع
true