Is Subsequence

Q: מהי סיבוכיות הזמן של Is Subsequence?

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

Q: למה גישת שני המצביעים החמדנית עובדת עבור Is Subsequence?

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

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

הכינו את t פעם אחת: עבור כל אות, שמרו את רשימת האינדקסים הממוינת שבהם היא מופיעה. כדי למקם את s[i] , חפשו בחיפוש בינארי ברשימה של אותה אות את האינדקס הראשון שאחרי ההתאמה הקודמת. כך כל בדיקה עולה O(n log m) במקום O(m) .

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

+10

נתונות לך שתי מחרוזות, s ו-t. החזר true אם אפשר להפוך את t ל-s על ידי מחיקת חלק מהאותיות שלה (ייתכן שאף אחת), כך שהאותיות שנותרו ישמרו על הסדר שלהן, ו-false אחרת. לדוגמה, ace היא תת-רצף של abcde, אבל aec אינה.

פונקציה

isSubsequence(s: string, t: string) → boolean

sstring: המחרוזת שאותה מחפשים
tstring: המחרוזת שממנה יש למחוק אותיות
מחזירהboolean: אמת אם אפשר לקרוא את s בתוך t לפי הסדר, אולי עם פערים

אילוצים

1 ≤ s.length ≤ 3 × 10⁴
1 ≤ t.length ≤ 5 × 10⁴
s ו־t מכילים אותיות אנגליות קטנות בלבד.

דוגמאות

קלט: s = "ace"t = "abcde"
פלט: true
הסבר: מחקו את b ואת d מתוך abcde, ונשאר ace באותו סדר.

קלט: s = "aec"t = "abcde"
פלט: false
הסבר: ל־t יש את כל שלוש האותיות, אבל ה־c היחיד נמצא לפני ה־e היחיד. אחרי השימוש ב־e שבאינדקס 4, לא נשאר c מימינו.

קלט: s = "moon"t = "monsoon"
פלט: true
הסבר: השתמשו ב־m שבאינדקס 0, ב־o שבאינדקסים 1 ו־4, וב־n שבאינדקס 6 של monsoon. האותיות שביניהם נמחקות.

+20 בדיקות נסתרות בשליחה

שאלת המשך

נניח ש-t נשארת ללא שינוי, ועליך לבדוק מיליון מחרוזות שונות s מולה. איך תכין את t כך שכל בדיקה תהיה מהירה יותר מקריאה מחדש של כל t?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

תכנות דינמי על קידומות

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

שאלו שאלה קטנה יותר: האם אפשר להתאים את i האותיות הראשונות של s בתוך j האותיות הראשונות של t? נסמן את התשובה ב־dp[i][j]. אם אפשר להתאים אותן בתוך t[:j-1], אפשר להתאים אותן גם בתוך t[:j], כי אפשר למחוק את t[j-1]. אם s[i-1] שווה ל־t[j-1], אפשר גם להשתמש באות הזאת, ואז צריך להתאים את i-1 האותיות הראשונות של s בתוך t[:j-1]. לכן dp[i][j] = dp[i][j-1] or (s[i-1] == t[j-1] and dp[i-1][j-1]), והקידומת הריקה של s מתאימה בכל מקום.

שורה i קוראת רק את שורה i-1, לכן מספיקות שתי שורות באורך m+1. התשובה היא התא האחרון בשורה האחרונה.

זו אותה טבלה שבונים עבור תת־הסדרה המשותפת הארוכה ביותר, והיא נכונה, אבל היא ממלאת כל תא. כאשר s מכילה 25,000 אותיות ו־t מכילה 50,000, מדובר ב־1.25 × 10^9 תאים, הרבה יותר ממה שנדרש במעבר יחיד על שתי המחרוזות.

אלגוריתם

צרו שורה prev של m+1 ערכים, כולם true: s ריקה מתאימה לכל קידומת של t.
עבור כל i מ-1 עד n, צרו שורה cur עם cur[0] = false.
עבור כל j מ-1 עד m, הגדירו את cur[j] כ-cur[j-1], או כ-prev[j-1] כאשר s[i-1] שווה ל-t[j-1].
החליפו את prev ב-cur.
החזירו את prev[m].

def isSubsequence(s, t):
    n, m = len(s), len(t)
    # prev[j]: the first i-1 letters of s fit inside t[:j]. An empty s fits anywhere.
    prev = [True] * (m + 1)
    for i in range(1, n + 1):
        cur = [False] * (m + 1)
        for j in range(1, m + 1):
            cur[j] = cur[j - 1] or (s[i - 1] == t[j - 1] and prev[j - 1])
        prev = cur
    return prev[m]

שני מצביעים עם התאמה חמדנית

האינטואיציה

קוראים את t משמאל לימין ושומרים מצביע i לאות הבאה של s שעדיין צריך למצוא. כאשר t[j] שווה ל-s[i], משתמשים בה ומקדמים את i. בכל מקרה, מקדמים את j. אם i מגיע לסוף של s, כל אות מצאה מקום בסדר הנכון.

למה בטוח לבחור בהתאמה הראשונה? נניח שמיקום אפשרי כלשהו משתמש בעותק מאוחר יותר של s[i]. החלפתו בעותק המוקדם ביותר שומרת על הסדר ומשאירה יותר מ-t מימין עבור שאר האותיות של s, ולכן הבחירה החמדנית לעולם אינה גורמת לאובדן מיקום אפשרי. עבור moon בתוך monsoon, המצביע לוקח את ה-o באינדקס 1, מדלג על n ועל s, לוקח את ה-o באינדקס 4 ומגיע ל-n באינדקס 6.

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

אלגוריתם

הגדר i = 0 עבור s ו־j = 0 עבור t.
כל עוד שני האינדקסים נמצאים בתוך המחרוזות שלהם, השווה בין s[i] לבין t[j].
אם הם שווים, הגדל את i.
הגדל את j בכל מקרה.
החזר האם i שווה לאורך של s.

def isSubsequence(s, t):
    i = j = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

מלכודות ומקרי קצה

לולאת שני המצביעים קצרה, והבאגים שלה נמצאים בקצוות.

חיפוש של כל אות מתוך s בכל מקום ב-t במקום אחרי ההתאמה הקודמת. כך מתקבלת aec בתוך abcde, אף שהסדר מופר.
שימוש באותו עותק של אות פעמיים. noon אינה תת-רצף של moon: ב-moon יש רק n אחת, באינדקס 3, והיא לא יכולה להיות גם האות הראשונה וגם האות האחרונה של noon.
החזרת תשובה לפי השאלה אם j הגיע לסוף של t. הלולאה מסתיימת שם לעיתים קרובות, בין אם s נמצאה ובין אם לא; רק i אומר לך.
שכחה ש-s יכולה להיות ארוכה יותר מ-t. עבור abc מול ab יש להחזיר false, והלולאה מחזירה זאת כל עוד היא נעצרת כשנגמרת t.
קריאת s[i] אחרי ש-i הגיע לסוף של s. ב-Python או ב-Java הקריאה הזו גורמת לשגיאה, לכן יש לבדוק את i לפני ההשוואה.

שאלות נפוצות4

מהי סיבוכיות הזמן של Is Subsequence?

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

למה גישת שני המצביעים החמדנית עובדת עבור Is Subsequence?

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

איך בודקים במהירות מחרוזות רבות מול אותו t?

הכינו את t פעם אחת: עבור כל אות, שמרו את רשימת האינדקסים הממוינת שבהם היא מופיעה. כדי למקם את s[i], חפשו בחיפוש בינארי ברשימה של אותה אות את האינדקס הראשון שאחרי ההתאמה הקודמת. כך כל בדיקה עולה O(n log m) במקום O(m).

מה ההבדל בין תת־רצף לתת־מחרוזת?

תת־מחרוזת היא רצף של אותיות עוקבות, ואילו תת־רצף יכול לדלג על אותיות כל עוד הסדר נשאר זהה. ace הוא תת־רצף של abcde, אבל אינו תת־מחרוזת שלו. כל תת־מחרוזת היא תת־רצף, אך לא להפך.

Python

def isSubsequence(s, t):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

s = "ace"
t = "abcde"

צפוי

true