Valid Palindrome
لديك سلسلة نصية s. احتفظ بحروفها وأرقامها فقط، واعتبر الأحرف الكبيرة والصغيرة متطابقة، ثم حدّد ما إذا كان النص المتبقي يُقرأ بالطريقة نفسها من اليسار إلى اليمين ومن اليمين إلى اليسار. أعد true إذا كان كذلك، وfalse خلاف ذلك.
تُتجاهل جميع الأحرف الأخرى، مثل . و! و? و: و; و- أو _. إذا لم تحتوِ s على أي حروف أو أرقام، فلن يتبقى شيء، ويُعدّ النص الفارغ متناظرًا.
الدالة
- sstring
- النص المراد التحقق منه، بما في ذلك علامات الترقيم
- تُرجعboolean
- صحيح إذا كانت الأحرف والأرقام في s تُقرأ بالطريقة نفسها في كلا الاتجاهين، مع تجاهل حالة الأحرف
القيود
1 ≤ s.length ≤ 5 × 104sيحتوي على أحرف إنجليزية وأرقام وعلامات الترقيم. ! ? : ; - _، دون مسافات.
أمثلة
- المدخلات
- s = "Was_it_a_car_or_a_cat_I_saw?"
- المخرجات
- true
- الشرح
- احذف الشرطات السفلية وعلامة الاستفهام وحوّل الأحرف الكبيرة إلى صغيرة: ستحصل على
wasitacaroracatisaw، وهي الكلمة نفسها عند قراءتها بالعكس.
- المدخلات
- s = "race-a-car"
- المخرجات
- false
- الشرح
- من دون الشرطات، يكون النص
raceacar. عند قراءته من اليمين، يبدأ بـracaبدلًا منrace: للحرفeفي المنتصف الحرفaبوصفه نظيره في الانعكاس، لذا فالإجابة هيfalse.
- المدخلات
- s = "Step-on-no-pets!"
- المخرجات
- true
- الشرح
- النص المُحتفَظ به هو
steponnopets. يطابق الحرف الكبيرSالحرفsالأخير لأن حالة الأحرف يتم تجاهلها، ولا تؤدي الواصلة و!أي دور.
+25 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك تحديد ذلك باستخدام ذاكرة إضافية O(1)، دون إنشاء نسخة منقّحة من s؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تجاهل علامات الترقيم للحظة. ما الأحرف من
sالتي تقارنها عملية التحقق من كون النص متناظرًا، وفي أي أزواج؟يُقارَن الحرف أو الرقم الأول بالأخير، والثاني بما قبل الأخير، وهكذا، بعد تحويل الأحرف إلى أحرف صغيرة. لا تشارك علامات الترقيم في المقارنة أبدًا، لذا فهي لا تفعل سوى إعاقة العثور على الزوج التالي.
تحرّك بمؤشر واحد إلى الأمام من البداية، وبالآخر إلى الخلف من النهاية. تجاوز بكل مؤشر أي حرف ليس حرفًا أو رقمًا، وقارن الحرفين عند الاحتفاظ بكليهما، وتوقّف عندما يلتقي المؤشران.
الحل
فحص التناظر نفسه مألوف: يجب أن يتطابق أول حرف محتفَظ به مع الأخير، والثاني مع ما قبل الأخير، وهكذا. ما يجعل هذه النسخة صعبة هو أن الأحرف التي تقارن بينها لا تقع عند فهارس متناظرة في s، لأن علامات الترقيم متناثرة بشكل غير متساوٍ على الجانبين. يمكنك إزالتها أولًا، أو ترك مؤشرين يتجاوزانها بينما يتحركان نحو بعضهما.
نظّف السلسلة النصية، ثم قارنها بنسختها المعكوسة
الفكرة
أنشئ النص الذي تسأل عنه المسألة فعلًا. مرّ على s، واحتفظ بكل حرف أو رقم بحالة أحرف صغيرة، وتجاوز كل ما عدا ذلك. بالنسبة إلى Step-on-no-pets!، ينتج عن ذلك steponnopets. والآن، السؤال هو سؤال متناظر النصوص المعتاد: هل هذا النص يساوي معكوسه؟
هذا صحيح لأن التنظيف يزيل الأحرف التي تقول المسألة تحديدًا إنها تُهمَل، ويوحّد حالة الأحرف التي تقول المسألة إنها تُهمَل. إذا لم يحتوِ s على أي حروف أو أرقام، فسيكون النص المنظَّف فارغًا، والنص الفارغ يساوي معكوسه، لذا تكون الإجابة true من دون حالة خاصة.
تُقرأ كل محرف مرة واحدة للتنظيف ومرة أخرى للمقارنة، لذا يكون الزمن O(n). تتطلب النسخة المنظَّفة ومعكوسها ذاكرة إضافية مقدارها O(n)، وهي الكلفة التي تتخلص منها الطريقة التالية.
الخوارزمية
- أنشئ نصًا فارغًا باسم
cleaned. - لكل حرف من
s، إذا كان حرفًا أو رقمًا، فأضِفه بحالة الأحرف الصغيرة. - اعكس
cleaned. - أعِد ما إذا كان
cleanedيساوي معكوسه.
def isPalindrome(s):
cleaned = [ch.lower() for ch in s if ch.isalnum()]
return cleaned == cleaned[::-1]مؤشّران يتجاوزان علامات الترقيم
الفكرة
توجد النسخة المنظَّفة فقط لتتمكن من مقارنة الأحرف المتناظرة. يمكنك إجراء المقارنة نفسها مباشرةً على s. ضع left عند الفهرس الأول وright عند الفهرس الأخير. في كل خطوة، إذا كان left يشير إلى علامة ترقيم، فحرّكه إلى اليمين؛ وإذا كان right يشير إلى علامة ترقيم، فحرّكه إلى اليسار. عندما يشير كلاهما إلى حرف أو رقم، قارنهما بعد تحويلهما إلى أحرف صغيرة. عدم التطابق يعني false؛ أما التطابق فيعني تحريك كلا المؤشرين خطوةً نحو الداخل.
لماذا يُعد هذا الفحص مكافئًا؟ يتوقف المؤشران دائمًا عند الحرف التالي الذي سيتم الإبقاء عليه من كل طرف، لذا يزوران الأزواج (أول حرف مُحتفَظ به، آخر حرف مُحتفَظ به)، (ثاني حرف مُحتفَظ به، ما قبل الأخير) وهكذا، وهي بالضبط الأزواج التي تفحصها المقارنة معكوسة الترتيب. في Abc-dcbX يكون الزوج الأول A وX، وتكون الإجابة false بعد مقارنة واحدة.
تحرّك كل خطوة مؤشرًا واحدًا على الأقل، ويتوقف المؤشران عندما يلتقيان، لذا تتكرر الحلقة n مرةً كحد أقصى. وباستثناء الفهرسين، لا يُخزَّن أي شيء، وهذا يعني استخدام ذاكرة إضافية بمقدار O(1).
الخوارزمية
- عيّن
left = 0وright = n-1. - طالما كان
left < right: إذا لم يكنs[left]حرفًا أو رقمًا، فزِدleftوتابع. - وإلا، إذا لم يكن
s[right]حرفًا أو رقمًا، فأنقِصrightوتابع. - وإلا، فقارن الحرفين بعد تحويلهما إلى أحرف صغيرة. إذا اختلفا، فأعِد
false؛ وإذا تطابقا، فحرّك المؤشرين نحو الداخل. - عندما يلتقي المؤشران، أعِد
true.
def isPalindrome(s):
left, right = 0, len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
elif not s[right].isalnum():
right -= 1
elif s[left].lower() != s[right].lower():
return False
else:
left += 1
right -= 1
return True
أخطاء شائعة وحالات حدّية
تأتي معظم الأخطاء من الأحرف التي يتم تخطيها ومن حالة الأحرف.
- مقارنة
s[i]بـs[n-1-i]في السلسلة الخام. تُعدa-baمتناظرة بعد حذف الشرطة، لكن الحرف المقابل للشرطة-عند الفهرس 1 في السلسلة الخام هوbعند الفهرس 2. - تحريك المؤشرين معًا عندما يكون أحدهما فقط عند علامة ترقيم. تخطَّ الأحرف في أحد الجانبين كل مرة، وإلا فلن يعود الجانبان متزامنين.
- تخطي علامات الترقيم في حلقة داخلية تتجاوز المؤشر الآخر. مع
?!-_، تتجاوز حلقة داخلية غير محدودة نهاية السلسلة؛ أبقِ على التحقق منleft < rightفي كل حركة. - اعتبار الأرقام أحرفًا غير مهمة.
0Pهيfalse: يُحتفَظ بالرقم0وتتم مقارنته، وهو ليس الحرفp. - إرجاع
falseعندما لا يُحتفَظ بأي شيء. السلسلة المكوّنة من علامات ترقيم فقط، مثل.، يكون نصها المنظَّف فارغًا، وهذا نص متناظر. - قد تُفسَّر السلسلة المكوّنة من أرقام فقط، مثل
12321، على أنها رقم في PHP وR. حوِّلها إلى سلسلة أولًا.
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة التحقق من كون النص متناظرًا؟
يعمل كلا الأسلوبين في زمن O(n)، لأن كل محرف يُفحَص عددًا ثابتًا من المرات. يتطلب التنظيف أولًا ذاكرة إضافية مقدارها O(n) للنسخة. يستخدم إصدار المؤشرين ذاكرة إضافية مقدارها O(1)، لأنه يحتفظ بمؤشرين فقط.
كيف تتحقق مما إذا كانت الكلمة متناظرة مع تجاهل الأحرف والأرقام؟
أبقِ مؤشرًا عند كل طرف من السلسلة النصية. حرّك مؤشرًا متجاوزًا أي حرف ليس حرفًا أو رقمًا، وعندما يستقر كلا المؤشرين على حرفين أو رقمين، قارنهما بعد تحويلهما إلى أحرف صغيرة. إذا تطابقت كل زوج من الأحرف المُقارَنة حتى التقاء المؤشرين، فالسلسلة النصية متناظرة.
هل السلسلة النصية الفارغة متناظرة؟
نعم. يُقرأ النص الفارغ بالطريقة نفسها في كلا الاتجاهين، لذا فإن سلسلة مثل ?!-_، التي يتم تجاهل جميع محارفها، تُرجع true. يحقق كلا النهجين ذلك من دون إضافة شيفرة: فالنص المنقّى يساوي معكوسه الفارغ، ولا يجد المؤشران زوجًا مختلفًا.
لماذا نستخدم مؤشرين بدلًا من عكس السلسلة النصية؟
يتطلب العكس نسخةً منظَّفة ونسخةً معكوسة، ما يستلزم ذاكرة إضافية مقدارها O(n). يقارن مؤشّران الأزواج نفسها في مكانها، ويمكنهما التوقف عند أول اختلاف، غالبًا بعد بضع خطوات. عادةً ما يطلب المحاورون هذه النسخة كسؤال متابعة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def isPalindrome(s):
# اكتب الشيفرة هناالحالة 1
الحالة 2
الحالة 3
المدخلات
s = "Was_it_a_car_or_a_cat_I_saw?"
المتوقع
true