Is Subsequence

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

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

Q: מה הקשר בין תת־רצף לרצף המשותף הארוך ביותר?

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

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

+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 and 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. האותיות שביניהם נמחקות.

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

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

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

האינטואיציה

נסמן ב־dp[i][j] אם האותיות הראשונות i של s מתאימות לאותיות הראשונות j של t. הן מתאימות אם הן כבר מתאימות בלי t[j-1], או אם s[i-1] שווה ל־t[j-1] והאותיות הראשונות i-1 מתאימות ל־t[:j-1]. הקידומת הריקה מתאימה בכל מקום, ושורה 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]

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

האינטואיציה

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

הלולאה קוראת כל אות ב־t לכל היותר פעם אחת ושומרת שני אינדקסים: זמן O(n + m) וזיכרון O(1).

אלגוריתם

הגדר את 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: ה-n היחידה, באינדקס 3, לא יכולה להיות גם האות הראשונה וגם האות האחרונה.
החזרה של השאלה האם j הגיע לסוף של t. הלולאה מסתיימת שם לעיתים קרובות, בין אם s נמצא ובין אם לא; רק i אומר לך.
אי-עצירה כשנגמר t. עבור abc מול ab יש להחזיר false.
קריאה של s[i] אחרי ש-i הגיע לסוף של s. ב-Python או ב-Java הקריאה הזאת גורמת לחריגה, לכן יש לבדוק את i לפני שמשווים.

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

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

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

מה הקשר בין תת־רצף לרצף המשותף הארוך ביותר?

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

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

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

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

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

s = "ace"
t = "abcde"

הפלט הצפוי

true