Longest Common Prefix

Q: מהי סיבוכיות הזמן של Longest Common Prefix?

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

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

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

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

האינטואיציה

התחילו בהנחה שהמילה הראשונה כולה היא התשובה. לאחר מכן השוו אותה למילה השנייה, אות אחר אות, וקצרו אותה לחלק המשותף להן. השוו את מה שנותר למילה השלישית, וכן הלאה. אחרי המילה האחרונה, מה שנותר משותף לכולן.

זה נכון כי הקידומת המשותפת למילים רבות היא הקידומת המשותפת לשתי המילים הראשונות, ואז לתוצאה הזאת ולמילה השלישית, וכן הלאה: בכל שלב אפשר רק לשמור עליה או לקצר אותה. עבור interview, internet, interval, internal, המועמדת מצטמצמת מ־interview ל־inter אחרי המילה השנייה ונשארת כך.

כל אות מושווית לכל היותר פעם אחת, ולכן זמן הריצה הוא O(S), כאשר S הוא מספר האותיות הכולל. שומרים רק את האורך, לא עותק. נקודת התורפה היא הסדר: עם 200 מילים בנות 200 אותיות, שבהן 199 המילים הראשונות זהות ורק המילה האחרונה שונה באות הראשונה שלה, משווים את כל 200 האותיות לכל אחת מ־199 המילים הראשונות, כמעט 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]

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

האינטואיציה

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

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

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

אלגוריתם

נסמן את strs[0] בתור first.
עבור כל עמודה 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

מהי סיבוכיות הזמן של Longest Common Prefix?

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

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

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

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

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

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

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

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

צפוי

"inter"