Letter Combinations of a Phone Number

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

זהו O(4^n · n) עבור n ספרות: ייתכנו 4^n מחרוזות, כאשר כל ספרה היא 7 או 9, ולכתיבת כל אחת מהן נדרשים n צעדים. כאשר יש רק מקשים עם שלוש אותיות, הסיבוכיות היא O(3^n · n) . שום פתרון לא יכול להיות יעיל יותר, כי זהו גודל הפלט. נסיגה לאחור דורשת O(n) מקום נוסף מלבד הפלט.

בינוניחיפוש לאחור

+10

בלוח המקשים של טלפון, לכל ספרה מ־2 עד 9 משויכות כמה אותיות: 2 היא abc, 3 היא def, 4 היא ghi, 5 היא jkl, 6 היא mno, 7 היא pqrs, 8 היא tuv ו־9 היא wxyz.

ניתנת לך מחרוזת digits. בחר אות אחת לכל ספרה, תוך שמירה על סדר הספרות, ותקבל מחרוזת אחת שהמקשים יכולים להקליד. החזר את כל המחרוזות האפשריות, ממוינות בסדר לקסיקוגרפי (מילוני). עבור "23" יש תשע מחרוזות כאלה, מ־"ad" עד "cf".

פונקציה

letterCombinations(digits: string) → string-array

digitsstring: הספרות שנלחצו, כל אחת מ־2 עד 9
מחזירהstring-array: כל מחרוזת שהמקשים יכולים להקליד, בסדר לקסיקוגרפי

אילוצים

1 ≤ digits.length ≤ 4
כל תו ב־digits הוא ספרה מ־2 עד 9.
התשובה מכילה לכל היותר 4⁴ = 256 מחרוזות.

דוגמאות

קלט: digits = "23"
פלט: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
הסבר: 2 מציע את a, b, c ו-3 מציע את d, e, f. כל אות ראשונה מצטרפת לכל אות שנייה, כך שיש 3 × 3 = 9 מחרוזות, ורישום שלהן כשהאות הראשונה משתנה לאט ביותר שומר על הסדר שלהן.

קלט: digits = "94"
פלט: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
הסבר: ל־9 יש ארבע אותיות ול־4 יש שלוש, ולכן יש 4 × 3 = 12 מחרוזות. כל שלוש המחרוזות שמתחילות ב־w מופיעות לפני המחרוזת הראשונה שמתחילה ב־x.

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

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

בנו את המחרוזות ספרה אחת בכל פעם

האינטואיציה

בנו את התשובות ספרה אחת בכל פעם. התחילו ברשימה שמכילה מחרוזת ריקה אחת. עבור "23", הספרה 2 הופכת אותה ל־a, b, c. הספרה 3 מרחיבה לאחר מכן כל אחת מהן באמצעות d, e ו־f, וכך מתקבלות תשע מחרוזות באורך 2. אחרי הספרה האחרונה, הרשימה מכילה את כל התשובות.

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

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

אלגוריתם

התחילו עם combos = [""], קידומת ריקה אחת.
עבור כל ספרה, צרו רשימה חדשה: עבור כל קידומת ב־combos ועבור כל אות במקש של אותה ספרה, הוסיפו prefix + letter.
החליפו את combos ברשימה החדשה.
אחרי הספרה האחרונה, החזירו את combos.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    combos = [""]  # every prefix built so far; one empty prefix to start
    for digit in digits:
        # Each old prefix grows by each letter of this digit, in order.
        combos = [prefix + letter for prefix in combos for letter in KEYPAD[digit]]
    return combos

חזרה לאחור לאורך עץ ההחלטות

האינטואיציה

חשוב על התשובה כעל עץ החלטה. השורש הוא מחרוזת ריקה. עבור "23" יש לו שלושה ילדים, a, b ו־c, אחד לכל אות של 2. לכל אחד מהם יש שלושה ילדים משלו, אחד לכל אות של 3. לעץ יש רמה אחת לכל ספרה, ותשעת העלים, מ־ad עד cf, הם בדיוק התשובות.

חיפוש עם חזרה עובר בעץ הזה לעומק באמצעות מאגר יחיד, path. ברמה i את בוחרת אות של digits[i] באמצעות הוספתה, חוקרת את כל מה שמתחתיה באמצעות קריאה רקורסיבית על i+1, ואז מבטלת את הבחירה באמצעות הסרת האות. הביטול הוא מה שמאפשר למאגר אחד לשמש את כל העץ: לאחר ששומרים את ad, את ae ואת af, הוצאת האות מחזירה את path ל־a, ואז למחרוזת הריקה, מוכנה עבור b. כאשר i שווה לאורך של digits, המאגר מכיל תשובה מלאה, ושומרים עותק שלה.

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

אלגוריתם

השאר נתיב ריק ו־path ריק ו־result ריק.
הגדר את backtrack(i): אם i שווה לאורך של digits, שמור עותק של path והחזר.
אחרת, עבור כל אות במקש של digits[i], לפי הסדר: הוסף אותה ל־path, קרא ל־backtrack(i+1), ואז הסר אותה.
קרא ל־backtrack(0) והחזר את result.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    result = []
    path = []  # the letters chosen so far, one per digit

    def backtrack(i):
        if i == len(digits):
            # Every digit has a letter: this leaf is one finished string.
            result.append("".join(path))
            return
        for letter in KEYPAD[digits[i]]:
            path.append(letter)   # choose
            backtrack(i + 1)      # explore the digits after this one
            path.pop()            # undo, so the next letter can take its place

    backtrack(0)
    return result

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

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

ההנחה שלכל מקש יש שלוש אותיות. במקשים 7 יש pqrs ובמקש 9 יש wxyz, לכן לקיחת שלוש אותיות מהאינדקס (d-2)*3 באלפבית משמיטה את s ממקש 7 ומתחילה את מקש 8 ב-s במקום ב-t. כתבו את לוח המקשים כטבלה.
שוכחים לבטל את הפעולה. אם לא מסירים את האות אחרי הקריאה הרקורסיבית, path ממשיך לגדול, והתשובה השנייה עבור "23" יוצאת ade במקום ae.
שומרים את המאגר במקום עותק. ב-Python, הפקודה result.append(path) שומרת את אותה רשימה תשע פעמים, ובסוף היא ריקה. שרשרו אותה למחרוזת חדשה כשאתם שומרים אותה.
מאבדים את הסדר. ניסיון לעבור על האותיות של מקש מימין לשמאל, או לבנות את המחרוזות מתוך מחסנית בגרסה האיטרטיבית, יוצר את התשובות בסדר שונה מהסדר הממוין שהבעיה מבקשת.
מחרוזת ספרות שנקראה כמספר. בשפות בעלות טיפוסיות רופפת, כגון PHP ו-R, ייתכן שתקבלו את "23" כמספר 23. הפכו אותו לטקסט לפני שתיגשו לתווים שלו לפי אינדקס.

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

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

זהו O(4^n · n) עבור n ספרות: ייתכנו 4^n מחרוזות, כאשר כל ספרה היא 7 או 9, ולכתיבת כל אחת מהן נדרשים n צעדים. כאשר יש רק מקשים עם שלוש אותיות, הסיבוכיות היא O(3^n · n). שום פתרון לא יכול להיות יעיל יותר, כי זהו גודל הפלט. נסיגה לאחור דורשת O(n) מקום נוסף מלבד הפלט.

האם תוכל לפתור את צירופי האותיות ללא רקורסיה?

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

למה חזרה לאחור מחזירה את הצירופים בסדר ממוין?

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

ומה לגבי הספרות 0 ו־1?

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

Python

def letterCombinations(digits):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

digits = "23"

צפוי

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]