على مر السنين ، أصبح التحقق مما إذا كانت السلسلة متناظرة أم لا سؤال مقابلة ترميزًا كلاسيكيًا. هذا لأنه يتضمن مفاهيم حول التلاعب بالسلسلة والمقارنة وحتى الحلقات اعتمادًا على التنفيذ. والسؤال ليس مطولًا ، لذا يمكن إكماله في حدود الوقت المحدد للمقابلة. تتضمن هذه المقالة تطبيقًا للتحقق مما إذا كانت سلسلة نصية متناظرة في Java و python.
ما هو Palindrome؟
وفقًا لموقع synonym.com ، فإن تعريف المتناظرة هو "كلمة أو عبارة تقرأ نفس الرجوع إلى الأمام." في الأساس ، يعني هذا أنه إذا كتبت الكلمة أو العبارة في الاتجاه المعاكس ، فستكون تمامًا كما كانت عندما تم إعادة توجيهها. على سبيل المثال ، الأب والأم متناظران والأب والأم ليسوا كذلك. تأتي كلمة "متناظرة" من كلمتين أساسيتين يونانيتين ، "بالين" تعني مرة أخرى و "دروموس" تعني الطريق أو الاتجاه. صاغها الكاتب المسرحي الإنجليزي بن جونسون في القرن السابع عشر.
حل
- الطريقة الأكثر شيوعًا وسهولة لحل السؤال هي عكس السلسلة أولاً ثم مقارنتها بالسلسلة الأصلية. سيكون هذا النهج O (n) في تدوين big-O لأن انعكاس السلسلة هو O (n).
- هناك طريقة أخرى تتمثل في بدء مقارنة الشخصيات من البداية والنهاية والاستمرار حتى تصل إلى الوسط. يحتوي هذا النهج على تعقيد زمني لـ O (n / 2) ولكن في تدوين big-O سيظل O (n). لكن ميزة هذا الأسلوب هي أنه يمكنك إرجاع False بمجرد أن تصادف عدم التطابق الأول ، بينما مع النهج الأول ، نظرًا لأن عكس سلسلة هو الخطوة الأولى ، سيكون التعقيد الزمني دائمًا هو O (n).
Palindrome في تنفيذ Python
فيما يلي رمز التحقق مما إذا كانت السلسلة متناظرة في Python.
def is_palindrome (s): "" "إرجاع صحيح إذا كانت الوسيطة المعطاة متطابقة أخرى خطأ" "" تأكيد (isinstance (s، str)) ، "الوسيطة ليست من النوع "# تأكيد ما إذا كانت الوسيطة المعطاة من النوع return s [:: - 1] == s # قارن عكس السلسلة مع نفسها إذا __name __ == "__ main__": print (is_palindrome ("dad")) def is_palindrome (word): "" "يقارن الأحرف واحدًا تلو الآخر من البداية والنهاية ويعيد False عند حدوث أول عدم تطابق أو يُرجع True" "i1، i2 = 0، len (word) -1 # تهيئة المؤشرات أثناء i2> i1: إذا كانت الكلمة [i1]! = الكلمة [i2]: # إذا كانت الأحرف غير متطابقة ، فلا داعي للاستمرار في العودة False i1 + = 1 i2- = 1 إرجاع True إذا __name __ == "__ main__ ": print (is_palindrome (" أبي ")) تطبيق Palindrome في Java
فيما يلي رمز التحقق مما إذا كانت السلسلة متناظرة في جافا.
الفئة العامة Palindrome {public static Boolean isPalindrome (String str) {StringBuilder sb = new StringBuilder (str)؛ // StringBuilder لديه طريقة عكسية ترجع sb.reverse (). toString (). equals (str)؛ // قارن عكس السلسلة مع نفسها} public static void main (String args []) {Boolean b = isPalindrome ("dad")؛ System.out.println (ب) ؛ }}فئة عامة Palindrome {public static Boolean isPalindrome (String str) {int i1 = 0؛ int i2 = str.length () - 1 ؛ while (i2> i1) {if (str.charAt (i1)! = str.charAt (i2)) {return false؛ } i1 ++ ؛ i2-- ؛ } عودة صحيحة؛ } public static void main (String args []) {Boolean b = isPalindrome ("dad")؛ System.out.println (ب) ؛ }} 
