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