Palindrome String

Q: איך בודקים אם מחרוזת היא פלינדרום?

השווה את התו הראשון לאחרון, את השני לזה שלפני האחרון, וכן הלאה לכיוון האמצע. אם זוג כלשהו שונה, המחרוזת אינה פלינדרום. שני אינדקסים שמתחילים בשני הקצוות ומתקדמים פנימה עושים זאת במעבר אחד.

Q: האם אפשר לבדוק אם מילה היא פלינדרום בלי זיכרון נוסף?

כן. בדיקת שני המצביעים קוראת את התווים במקומם ושומרת שני אינדקסים, ולכן משתמשת במקום נוסף של O(1) . השוואת s עם ההיפוך שלו קצרה יותר לכתיבה, אבל יוצרת מחרוזת שנייה של n תווים.

Q: מהי סיבוכיות הזמן של בדיקת מחרוזת פלינדרומית?

O(n) עבור מחרוזת באורך n . הבדיקה באמצעות שני מצביעים מבצעת לכל היותר n / 2 השוואות ועוצרת באי-התאמה הראשונה, לכן coddy דורשת השוואה אחת.

Q: האם תו יחיד הוא פלינדרום?

כן, הקריאה זהה בשני הכיוונים. בלולאת שני המצביעים left ו- right מתחילים שניהם באינדקס 0, הלולאה לעולם לא פועלת, והפונקציה מחזירה true .

מתחיליםשני מצביעים מערכים ומחרוזות

+10

מחרוזת היא פלינדרום כאשר קוראים אותה משמאל לימין ומימין לשמאל באותו אופן, כמו level. כתוב פונקציה שמקבלת מחרוזת s שמורכבת מאותיות קטנות באנגלית ומחזירה true אם s היא פלינדרום, ו-false אחרת.

פונקציה

isPalindrome(s: string) → boolean

sstring: המחרוזת באותיות קטנות שיש לבדוק
מחזירהboolean: נכון כאשר s נקראת באותה צורה בשני הכיוונים

אילוצים

1 ≤ s.length ≤ 5 × 10⁴
s מכיל רק אותיות אנגליות קטנות (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 ייחשב לפלינדרום?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

פלינדרום שווה להיפוך של עצמו, לכן אפשר לבנות את ההיפוך ולהשוות ביניהם. אין צורך בעותק: התו הראשון חייב להתאים לתו האחרון, השני לזה שלפני האחרון, וכן הלאה. שני אינדקסים שמתקדמים פנימה בודקים את הזוגות האלה במקום ועוצרים בחוסר ההתאמה הראשון.

השוו את המחרוזת למחרוזת ההפוכה שלה

האינטואיציה

הפוך את 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 משווה בין שני מצביעים, ולכן הוא מחזיר false עבור עותק; יש להשתמש ב-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