Valid Palindrome

Q: מהי סיבוכיות הזמן של Valid Palindrome?

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

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

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

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

כן. טקסט ריק נקרא באותו אופן בשני הכיוונים, ולכן מחרוזת כגון ?!-_ , שכל התווים בה מתעלמים, מחזירה true . שתי הגישות משיגות זאת ללא קוד נוסף: הטקסט לאחר הניקוי שווה להיפוך הריק שלו, ושני המצביעים לעולם לא מוצאים זוג ששונה.

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

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

קלשני מצביעים

+10

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

מתעלמים מכל תו אחר, כגון ., !, ?, :, ;, - או _. אם אין ב-s אותיות או ספרות כלל, לא נותר דבר, וטקסט ריק נחשב לפלינדרום.

פונקציה

isPalindrome(s: string) → boolean

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

אילוצים

1 ≤ s.length ≤ 5 × 10⁴
s מכיל אותיות באנגלית, ספרות וסימני הפיסוק . ! ? : ; - _, ללא רווחים.

דוגמאות

קלט: 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?

רמזים

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

נפתחו 0 מתוך 3

פתרון

בדיקת הפלינדרום עצמה מוכרת: התו הראשון שנשאר חייב להיות שווה לאחרון, השני חייב להיות שווה לתו שלפני האחרון, וכן הלאה. מה שמסבך את הגרסה הזאת הוא שהתווים שמשווים אינם נמצאים באינדקסים סימטריים של 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

מהי סיבוכיות הזמן של Valid Palindrome?

שתי הגישות פועלות בזמן 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