Word Search

Q: מהי סיבוכיות הזמן של Word Search?

המקרה הגרוע ביותר הוא O(m·n·3^L) עבור לוח בגודל m × n ומילה באורך L . כל אחד מ־ m·n התאים יכול להתחיל מסלול, ואחרי הצעד הראשון יש לכל תא לכל היותר שלושה שכנים שלא ביקרנו בהם שאפשר לנסות. המקום הנוסף הוא O(L) עבור הרקורסיה, ועוד O(m·n) אם מעתיקים את הלוח כדי לסמן בו תאים.

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

+10

נתונה לך רשת של אותיות board, המיוצגת כרשימה של מחרוזות, שבה board[r][c] היא האות בשורה r, בעמודה c, ומחרוזת word.

החזר true אם אפשר לעקוב אחר word ברשת: מתחילים בכל תא, ובכל צעד עוברים לתא שמעל התא הנוכחי, מתחתיו, משמאלו או מימינו, כך שהאותיות בתאים שבהם מבקרים מרכיבות את word לפי הסדר. אסור להשתמש באותו תא יותר מפעם אחת במהלך המעקב. אחרת, החזר false. האותיות תלויות רישיות, לכן a ו-A הן אותיות שונות.

פונקציה

exist(board: string-array, word: string) → boolean

boardstring-array: הרשת, מחרוזת אותיות אחת בכל שורה
wordstring: המילה למעקב
מחזירהboolean: האם ניתן לעקוב אחר המילה דרך תאים סמוכים, כאשר משתמשים בכל תא לכל היותר פעם אחת

אילוצים

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6, ולכל השורות יש אותו אורך.
1 ≤ word.length ≤ 20
board ו-word מכילים אותיות באנגלית בלבד, גדולות וקטנות.

דוגמאות

קלט: board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
פלט: true
הסבר: התחל ב-S בשורה 0, בעמודה 0, ואז עבור ימינה אל T, למטה אל O, ימינה אל ה-O השני, ימינה אל L, ולמטה אל ה-S שבשורה 2, בעמודה 3. אלה שישה תאים שונים, שכל אחד מהם סמוך לתא שלפניו.

קלט: board = ["STAR", "POOL", "ENDS"]word = "POP"
פלט: false
הסבר: בלוח יש P יחיד, בשורה 1, בעמודה 0. אחרי P ו־O דרוש לך עוד P, והיחיד נמצא בתא שבו המסלול התחיל, שאי אפשר להשתמש בו פעמיים.

קלט: board = ["STAR", "POOL", "ENDS"]word = "SAND"
פלט: false
הסבר: כל האותיות של SAND נמצאות בלוח, אבל המסלול נקטע כבר בצעד הראשון: ה-A היחידה נמצאת בשורה 0, בעמודה 2, ואף אחד משני ה-S אינו נוגע בה.

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

שאלת המשך

במקום לענות כן או לא, האם תוכל לספור כמה מסלולים שונים של word יש בלוח?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

חזרה לאחור עם רשת של תאים שבהם ביקרנו

האינטואיציה

דמיינו עץ החלטה. הבחירה הראשונה היא תא ההתחלה, והוא חייב להכיל את word[0]. לאחר מכן, כל צומת הוא מסלול שמאיית את i האותיות הראשונות, והילדים שלו הם השכנים שמכילים את word[i] ועדיין אינם נמצאים במסלול. מסלול שמאיית את המילה כולה הוא הצלחה. מסלול שאין לו שכן כזה הוא מבוי סתום, ואז חוזרים אחורה כדי לנסות את הבחירה הבאה.

לוח visited אוכף את הכלל שמותר להשתמש בכל תא פעם אחת. מסמנים תא כשהמסלול נכנס אליו ומבטלים את הסימון כשהמסלול יוצא ממנו. ביטול הסימון הוא מה שמאפשר את החזרה לאחור: תא שעברו בו במבוי סתום חייב להתפנות שוב כדי שאפשר יהיה לנסות שוב. בלוח AA / AB עם המילה AAA, אם מתחילים בתא השמאלי העליון, ירידה למטה נתקעת בתא השמאלי התחתון (השכן האחר שלו הוא B), ומעבר ימינה נתקע בתא הימני העליון. אם התאים האלה היו נשארים מסומנים, לעולם לא היה אפשר למצוא את התשובה: התא השמאלי התחתון, אחריו התא השמאלי העליון ואז התא הימני העליון.

זוהי התשובה המקובלת, והיא נכונה ומהירה מספיק במקרה הזה. העלות שלה היא מספר המסלולים שהיא בודקת. אחרי הצעד הראשון, בכל צעד יש לכל היותר שלושה כיוונים חדשים, ולכן מילה באורך L אותיות עשויה להוביל לסדר גודל של m·n·3^L מסלולים. נניח שיש לוח בגודל 5 × 5 שכולו מלא ב-A, והמילה מורכבת מ-8 אותיות A ואחריהן B. כל מסלול של אותיות A הוא תחילית תקפה, והחיפוש עובר על כולם לפני שהוא מגלה שאין B: בערך 65,000 בדיקות תאים כדי להחזיר false. כל אות נוספת בערך מכפילה את המספר הזה, ולכן בגישה הבאה בודקים כמה דברים לפני החיפוש.

אלגוריתם

צרו מערך visited בגודל הלוח, שבו כל הערכים הם false.
הגדירו dfs(r, c, i): החזירו false אם (r, c) נמצא מחוץ למערך, כבר סומן כ־visited, או שהאות שלו אינה word[i].
אם i הוא האינדקס האחרון של word, החזירו true.
סמנו את (r, c) כ־visited, נסו את ארבעת התאים השכנים עם i+1, ואז בטלו את הסימון והחזירו האם אחד מהשכנים הצליח.
קראו ל־dfs(r, c, 0) מכל תא והחזירו true ברגע שאחד מהם מצליח.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    visited = [[False] * cols for _ in range(rows)]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if visited[r][c] or board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        visited[r][c] = True   # mark: the current path owns this cell
        found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                 or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        visited[r][c] = False  # restore: other paths may use it
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

חזרה לאחור עם סימונים במקום וגיזום

האינטואיציה

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

שנית, צמצם את החיפוש לפני שמתחילים בו. ספור את האותיות. אם המילה זקוקה ליותר עותקים של אות מסוימת ממה שיש בלוח, התשובה היא false בלי לבצע חיפוש כלל. כך אפשר לענות על הלוח שכולו A, ובו 8 אותיות A ואות B, בלי חיפוש כלל, במקום לבצע כ־65,000 בדיקות. התחל מהקצה הנדיר יותר. מסלול שנקרא לאחור מאיית את המילה ההפוכה על אותם תאים, ולכן אפשר לחפש את המילה ההפוכה במקום זאת. אם האות האחרונה נדירה יותר בלוח מהאות הראשונה, הפוך את המילה. כך יש פחות תאים שמהם אפשר להתחיל חיפוש, והאות הנדירה פוסלת התחלות שגויות כבר בשלב הראשון במקום בשלב האחרון.

הכלל השני חשוב כשהאות הנדירה קיימת, אבל אינה נגישה. מקם את האות B היחידה בפינה ששני התאים הסמוכים לה הם C, וחפש 8 אותיות A ולאחריהן אות B. ספירת האותיות מצליחה. בחיפוש קדימה, החיפוש עדיין עובר על כל המסלולים של אותיות A, כ־35,000 בדיקות תאים. בחיפוש לאחור, המילה מתחילה ב־B, יש רק תא אחד שממנו אפשר להתחיל, השכנים שלו אינם A, והחיפוש מסתיים אחרי כ־30 בדיקות.

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

אלגוריתם

ספרו כל אות בלוח ובמילה. אם המילה דורשת יותר עותקים של אות כלשהי מאלה שיש בלוח, החזירו false.
אם יש בלוח יותר עותקים של word[0] מאשר של האות האחרונה, הפכו את word.
העתיקו את הלוח לרשת של תווים שאפשר לשנות.
הגדירו dfs(r, c, i): החזירו כישלון אם התא אינו word[i]; החזירו הצלחה אם i הוא האינדקס האחרון; אחרת, הגדירו את התא כ-#, נסו כל שכן שנמצא בגבולות עם i+1, החזירו את האות למקומה, והחזירו האם אחד מהניסיונות הצליח.
הריצו dfs(r, c, 0) מכל תא והחזירו true ברגע שאחד הניסיונות מצליח.

from collections import Counter


def exist(board, word):
    rows, cols = len(board), len(board[0])

    # Pruning 1: the board must hold every letter as many times as the word uses it.
    have = Counter("".join(board))
    for letter, need in Counter(word).items():
        if have[letter] < need:
            return False

    # Pruning 2: a path read backwards is the same path, so start from the
    # end whose letter is rarer on the board: fewer cells begin a search.
    if have[word[0]] > have[word[-1]]:
        word = word[::-1]

    grid = [list(row) for row in board]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if grid[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        grid[r][c] = "#"  # mark: "#" matches no letter, so this path cannot reuse the cell
        found = False
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
                found = True
                break
        grid[r][c] = word[i]  # restore the letter for other paths
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

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

רוב התשובות השגויות נובעות מסימון התאים ומבדיקות הגבולות.

לא מבטלים את הסימון של תא לאחר שענף נכשל. התא נשאר חסום לכל המסלולים הבאים, וב־AA / AB המילה AAA מחזירה false.
לא מסמנים כלל. בלי הסימון, המסלול יכול לחזור לתא שממנו הגיע, ו־POP בלוח לדוגמה יחזיר true.
קוראים את התא לפני בדיקת הגבולות. ב־Python, ‏board[-1] היא השורה האחרונה, ולא שגיאה, ולכן בדיקת גבולות חסרה גורמת בשקט לגלישה לצד השני של הרשת.
בודקים הצלחה רק לאחר מעבר. מילה בת אות אחת בלוח של תא אחד, ["A"] עם A, חייבת להחזיר true אף שלתא אין שכנים.
מסמנים באמצעות תו שיכול להיות אות אמיתית. שינוי האותיות בתא לאותיות גדולות או קטנות, למשל, ייכשל בלוחות שבהם מופיעות גם a וגם A.
נעים באלכסון. רק ארבעת התאים שחולקים צלע נחשבים לשכנים.

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

מהי סיבוכיות הזמן של Word Search?

המקרה הגרוע ביותר הוא O(m·n·3^L) עבור לוח בגודל m × n ומילה באורך L. כל אחד מ־m·n התאים יכול להתחיל מסלול, ואחרי הצעד הראשון יש לכל תא לכל היותר שלושה שכנים שלא ביקרנו בהם שאפשר לנסות. המקום הנוסף הוא O(L) עבור הרקורסיה, ועוד O(m·n) אם מעתיקים את הלוח כדי לסמן בו תאים.

למה מסירים את הסימון מתאים בחיפוש מילים?

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

איך גיזום הופך את חיפוש המילים למהיר יותר?

שתי בדיקות מתבצעות לפני החיפוש. אם המילה זקוקה לכמות גדולה יותר של אות מסוימת מזו שהלוח מכיל, אפשר להחזיר false בלי לחפש. ומכיוון שמסלול שנקרא לאחור מאיית את המילה ההפוכה, אפשר להתחיל מאיזה קצה שיש בו את האות הנדירה יותר, וכך לצמצם את מספר תאי ההתחלה ולפסול מסלולים שגויים מוקדם יותר. אף אחת מהבדיקות לא משנה את המקרה הגרוע ביותר, והחיפוש הפשוט הוא תשובה מלאה בפני עצמו. בלוח בגודל 5 × 5 שמורכב מ־A, עם מילה שזקוקה ל־B שחסרה בו, הן מצמצמות בערך 65,000 בדיקות תאים לאפס.

מה ההבדל בין Word Search ל־Word Search II?

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

Python

def exist(board, word):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

board = ["STAR", "POOL", "ENDS"]
word = "STOOLS"

צפוי

true