Longest Common Prefix

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

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

Q: מה על Longest Common Prefix להחזיר כשאין קידומת משותפת?

המחרוזת הריקה "" . זה קורה ברגע ששתי מילים מתחילות באותיות שונות, כמו stack , queue ו־ heap .

Q: מה עדיף, סריקה אופקית או אנכית?

לשניהם יש אותו מקרה גרוע ביותר, O(S) . סריקה אנכית היא הבחירה הבטוחה יותר: היא נעצרת בעמודה הראשונה שבה מילה כלשהי אינה תואמת, ואילו סריקה אופקית יכולה להשוות קידומת ארוכה למילים רבות לפני שמילה מאוחרת מקצרת אותה.

קלמערכים ומחרוזות

+10

ניתן לך מערך של מילים strs. החזר את המחרוזת הארוכה ביותר שכל מילה מתחילה בה. אם המילים לא מתחילות כולן באותה אות, החזר את המחרוזת הריקה "". מילה נחשבת לתחילית של עצמה, ולכן מילה בודדת היא התשובה שלה.

פונקציה

longestCommonPrefix(strs: string-array) → string

strsstring-array: המילים להשוואה
מחזירהstring: התחילית הארוכה ביותר המשותפת לכל המילים, או מחרוזת ריקה

אילוצים

1 ≤ strs.length ≤ 200
1 ≤ strs[i].length ≤ 200
כל מילה מכילה רק אותיות קטנות באנגלית.

דוגמאות

קלט: strs = ["interview", "internet", "interval", "internal"]
פלט: "inter"
הסבר: כל ארבע המילים מתחילות ב־inter. במיקום הבא, ל־interview ול־interval יש v, ול־internet ול־internal יש n, ולכן הקידומת נעצרת שם.

קלט: strs = ["stack", "queue", "heap"]
פלט: ""
הסבר: המילים מתחילות באותיות s, q ו־h. הן שונות כבר באות הראשונה, ולכן התשובה ריקה.

קלט: strs = ["prefix", "pre", "prepare"]
פלט: "pre"
הסבר: pre היא המילה הקצרה ביותר ושתי האחרות מתחילות בה, ולכן היא התשובה כולה. תחילית משותפת לעולם לא יכולה להיות ארוכה יותר מהמילה הקצרה ביותר.

שאלת המשך

נניח שהרשימה נשארת קבועה ומתקבלות שאילתות רבות. איך תמצאו עבור כל שאילתה את הקידומת הארוכה ביותר המשותפת לה ולמילה כלשהי ברשימה, בלי לסרוק מחדש את הרשימה?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

צמצמו את הקידומת מילה אחר מילה

האינטואיציה

נניח שכל המילה הראשונה היא התשובה. קצרו אותה לחלק המשותף לה ולמילה השנייה, ואז למילה השלישית, וכך הלאה. הקידומת המשותפת למילים רבות היא הקידומת המשותפת לשתי המילים הראשונות, ואז לזו ולמילה השלישית: בכל שלב אפשר רק להשאיר אותה כפי שהיא או לקצר אותה. לדוגמה 1, המועמדת משתנה מ־interview ל־inter אחרי המילה השנייה ונשארת כך.

כל אות מושווית לכל היותר פעם אחת, לכן זמן הריצה הוא O(S) עבור S אותיות בסך הכול. נקודת התורפה היא הסדר: עם 200 מילים בנות 200 אותיות, שבהן רק המילה האחרונה שונה באות הראשונה שלה, תבצעו קרוב ל־40,000 השוואות לפני שהמילה האחרונה תקצר את הקידומת לאפס.

אלגוריתם

הגדר את prefixLen לאורך של strs[0].
עבור כל מילה אחרת, ספור כמה אותיות ראשונות משותפות לה ול־strs[0], עד prefixLen.
הגדר את prefixLen למספר הזה, והפסק מוקדם אם הוא מגיע ל־0.
החזר את prefixLen האותיות הראשונות של strs[0].

def longestCommonPrefix(strs):
    first = strs[0]
    prefix_len = len(first)
    for word in strs[1:]:
        common = 0
        while common < prefix_len and common < len(word) and word[common] == first[common]:
            common += 1
        prefix_len = common
        if prefix_len == 0:
            break
    return first[:prefix_len]

השווה עמודה אחר עמודה

האינטואיציה

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

התשובה היא בדיוק רצף העמודות שבהן כל המילים תואמות, והלולאה הזאת עוברת על הרצף משמאל ועוצרת במקום שבו הוא נשבר. אם שום דבר לא שובר אותו, strs[0] היא התשובה.

עבור n מילים ותשובה באורך L, הלולאה מבצעת לכל היותר n × (L+1) בדיקות, וזה גם O(S). במקרה שבו רק האחרונה מבין 200 מילים שונה באות הראשונה שלה, היא עוצרת לאחר 199 השוואות.

אלגוריתם

נסמן את first בתור strs[0].
עבור כל עמודה col מ־0 ועד אורך first פחות אחד, נקרא את first[col].
עבור כל מילה אחרת, אם אין בה אות במיקום col או שהאות שלה שונה, נחזיר את col האותיות הראשונות של first.
אם כל העמודות תואמות, נחזיר את first.

def longestCommonPrefix(strs):
    first = strs[0]
    for col in range(len(first)):
        for word in strs[1:]:
            if col == len(word) or word[col] != first[col]:
                return first[:col]
    return first

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

קריאה מעבר לסוף של מילה קצרה יותר. בתוך prefix, pre, prepare, עמודה 3 קיימת ב-prefix אך לא ב-pre; בדקו את האורך לפני קריאת האות.
השוואה של המילה הראשונה והאחרונה בלבד בלי למיין. בתוך abc, xbd, abd שתי המילים האלה חולקות את ab, אבל xbd שוברת את עמודה 0 והתשובה ריקה.
החזרה של null או של מציין מקום כשאין חלק משותף. התשובה היא המחרוזת הריקה.
שכחה שמילה יחידה היא הקידומת של עצמה: algorithm לבדה מחזירה algorithm.
הוספת אות אחת בכל פעם למחרוזת בלתי ניתנת לשינוי. תשובה באורך 200 אותיות תצריך אז 200 העתקות; שמרו את האורך וחתכו פעם אחת מתחילת המילה הראשונה.

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

מהי סיבוכיות הזמן של הקידומת המשותפת הארוכה ביותר?

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

האם תוכל למצוא את הקידומת המשותפת הארוכה ביותר על ידי מיון המילים?

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

מה על Longest Common Prefix להחזיר כשאין קידומת משותפת?

המחרוזת הריקה "". זה קורה ברגע ששתי מילים מתחילות באותיות שונות, כמו stack, queue ו־heap.

מה עדיף, סריקה אופקית או אנכית?

לשניהם יש אותו מקרה גרוע ביותר, O(S). סריקה אנכית היא הבחירה הבטוחה יותר: היא נעצרת בעמודה הראשונה שבה מילה כלשהי אינה תואמת, ואילו סריקה אופקית יכולה להשוות קידומת ארוכה למילים רבות לפני שמילה מאוחרת מקצרת אותה.

def longestCommonPrefix(strs):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

strs = ["interview", "internet", "interval", "internal"]

הפלט הצפוי

"inter"