Word Ladder
מקבלים שתי מילים, beginWord ו-endWord, ורשימת מילים wordList. סולם הוא רצף של מילים שמתחיל ב-beginWord, מסתיים ב-endWord, ובכל מעבר ממילה למילה אחריה משתנה בדיוק אות אחת. כל מילה אחרי beginWord חייבת להופיע ב-wordList.
החזירו את מספר המילים בסולם הקצר ביותר, כולל שתי המילים שבקצותיו, או 0 אם לא קיים סולם. לדוגמה, cold, cord, card הם סולם בן 3 מילים. beginWord לא חייבת להופיע ב-wordList, אבל endWord חייבת.
פונקציה
- beginWordstring
- המילה הראשונה בסולם
- endWordstring
- המילה שאליה הסולם חייב להגיע
- wordListstring-array
- המילים שמהן חייב להגיע כל שלב מאוחר יותר
- מחזירהinteger
- מספר המילים בסולם הקצר ביותר, או 0 אם אין כזה
אילוצים
1 ≤ beginWord.length ≤ 10- ל-
endWordולכל מילה ב-wordListיש אותו אורך כמו ל-beginWord. 1 ≤ wordList.length ≤ 5000- כל המילים מורכבות מאותיות אנגליות קטנות בלבד.
beginWord != endWord- כל המילים ב־
wordListשונות זו מזו. ייתכן ש־beginWordהיא אחת מהן, וייתכן שלא.
דוגמאות
- קלט
- beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
- פלט
- 4
- הסבר
- המילים
leadו־goldשונות בשלוש אותיות, לכן אין מסלול מילים עם פחות מ־4 מילים, ולמסלולlead,load,goad,goldיש בדיוק 4 מילים. גםlendו־lewdשונות באות אחת מ־lead, אבל אף אחת מהן לא מובילה למקום חדש, ואלboldאפשר להגיע רק מ־goldעצמו.
- קלט
- beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
- פלט
- 0
- הסבר
cat,cot,cogנמצאות במרחק של אות אחת מ־dog, אבלdogלא נמצאת ברשימה, ולכן שום סולם לא יכול להסתיים שם.
- קלט
- beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
- פלט
- 3
- הסבר
ab,ad,cdוגםab,cb,cdכוללים 3 מילים.abמופיעה גם ברשימה, אבל מילת ההתחלה נספרת פעם אחת בכל מקרה.
+14 בדיקות נסתרות בשליחה
שאלת המשך
האם תוכל להחזיר סולם מילים קצר ביותר אחד, עם המילים לפי הסדר, ולא רק את אורכו?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
דמיינו כל מילה כנקודה, ושרטטו קו בין שתי מילים שנבדלות זו מזו בדיוק באות אחת. מהי סולם בתמונה הזו, ומהו הסולם הקצר ביותר?
הסולם הקצר ביותר הוא המסלול עם מספר השורות הקטן ביותר, ולכל שורה יש אותו משקל. חיפוש לרוחב מגיע לכל המילים שנמצאות במרחק צעד אחד לפני שהוא מגיע למילה כלשהי שנמצאת במרחק שני צעדים, ולכן בפעם הראשונה שהוא מגיע אל
endWordהוא השתמש במספר הצעדים הקטן ביותר. סמן מילה כמילה שביקרת בה ברגע שהגעת אליה לראשונה.השוואת מילה לכל הרשימה כדי למצוא את השכנות שלה היא איטית. במקום זאת, מסתירים אות אחת בכל פעם:
hot,hatו־hitהופכות כולן ל־h*t. מכניסים כל מילה לדלי של כל אחת מהתבניות שלה. השכנות של מילה הן המילים האחרות בדליים שלה. מריצים את החיפוש רמה אחר רמה, החל מ־beginWord, וסופרים את הרמות.
פתרון
התייחסו למילים כאל הצמתים של גרף, עם קשת בין שתי מילים שנבדלות באות אחת. סולם הוא מסלול מ־beginWord ל־endWord, ולכל הקשתות אותו משקל, ולכן הסולם הקצר ביותר הוא המסלול עם מספר הקשתות הקטן ביותר. חיפוש לרוחב מוצא בדיוק מסלול כזה. מה שהופך את הבעיה לקשה הוא מציאת הקשתות במהירות: השוואת כל זוג מתוך 5,000 מילים כרוכה ב־25 מיליון השוואות, ולכן הפתרון הטוב ביותר מוצא שכנים באמצעות תבניות עם תווים כלליים. בהמשך, n הוא מספר המילים ו־L הוא אורכן.
נסה כל סולם באמצעות חיפוש לעומק
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
מתחילים ב־beginWord. מהמילה הנוכחית, מנסים כל מילה שלא נעשה בה שימוש ונבדלת ממנה באות אחת, וממשיכים ממנה הלאה. כשמגיעים אל endWord, מתעדים את אורך סולם המילים אם הוא הקצר ביותר עד כה. מסמנים את המילים במסלול הנוכחי כמשומשות כדי שסולם המילים לא יחזור על עצמו, ומשחררים כל מילה כשחוזרים ממנה כדי שסולמות מילים אחרים יוכלו להשתמש בה. ברגע שיש סולם מילים עם best מילים, מפסיקים להרחיב כל מסלול שכבר יש בו best-1 מילים: הוא לא יכול להסתיים בסולם קצר יותר.
הפתרון נכון כי הוא מנסה כל סולם מילים שלא חוזר על מילה, וסולם מילים קצר ביותר לעולם לא חוזר על מילה: אם מילה הופיעה פעמיים, הסרת החלק שבין שתי ההופעות תיצור סולם מילים קצר יותר.
הפתרון איטי כי מספר סולמות המילים מתפוצץ. ניקח 26 מילים שנבדלות רק באות הראשונה שלהן, aaa, baa ועד zaa: כל זוג נבדל באות אחת, ולכן החיפוש יכול לעבור ביניהן בכל סדר לפני שהוא ממשיך הלאה, וניתן לסדר 26 מילים בכ־4 × 10^26 דרכים. הקיטום עוזר רק אחרי שנמצא סולם מילים כלשהו. כשאי אפשר להגיע אל endWord כלל, שום דבר לא נקטם, ורשימה של 34 מילים כבר גדולה מכדי שהחיפוש יוכל להשלים. גם הרקורסיה מגיעה לעומק של סולם המילים, שעשוי להכיל אלפי מילים.
אלגוריתם
- סמנו את
beginWordכמשומשת אם היא נמצאת ברשימה, והגדירו אתbestל־0. - כתבו את
search(word, length). אםwordהיאendWord, שמרו אתlengthאם הוא משפר אתbest, וחזרו. - אם
bestאינו 0 ו־length + 1 ≥ best, חזרו: הנתיב הזה לא יכול לנצח. - עבור כל מילה לא משומשת שנבדלת באות אחת מ־
word, סמנו אותה כמשומשת, קראו ל־search(next, length + 1), ואז בטלו את סימונה. - קראו ל־
search(beginWord, 1)והחזירו אתbest, שיישאר 0 אם לא קיימת שרשרת.
def ladderLength(beginWord, endWord, wordList):
def one_letter_apart(a, b):
differences = 0
for x, y in zip(a, b):
if x != y:
differences += 1
if differences > 1:
return False
return differences == 1
best = 0 # words in the shortest sequence found so far, 0 while there is none
used = [word == beginWord for word in wordList] # words on the current path
def search(word, length):
nonlocal best
if word == endWord:
if best == 0 or length < best:
best = length
return
if best != 0 and length + 1 >= best:
return # any longer path cannot beat the best one
for i, candidate in enumerate(wordList):
if not used[i] and one_letter_apart(word, candidate):
used[i] = True
search(candidate, length + 1)
used[i] = False # free the word for other paths
search(beginWord, 1)
return bestחיפוש לרוחב, השוואה בין כל זוג
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
חיפוש לרוחב בוחן את המילים לפי סדר המרחק. תחילה beginWord, סולם של מילה אחת. אחר כך כל מילה שנמצאת במרחק של אות אחת ממנה, סולמות של 2 מילים. אחר כך כל מילה חדשה שנמצאת במרחק של אות אחת מהמילים האלה, סולמות של 3 מילים, וכן הלאה. תור שומר על הסדר הזה: מילים יוצאות ממנו לפי סדר כניסתן, ולכן כל המילים במרחק d יוצאות לפני כל מילה במרחק d + 1.
בגלל הסדר הזה, הסולם הראשון שחיפוש לרוחב מוצא הוא הקצר ביותר. כשמילה מגיעה לראשונה במרחק d, כל מילה קרובה יותר מ-d כבר נבחנה, ולכן אילו היה קיים אליה סולם קצר יותר, החיפוש היה מגיע אליה קודם. אותו היגיון מראה שבטוח לסמן מילה ככזו שביקרנו בה ברגע שהיא נכנסת לתור: המרחק שלה סופי, והגעה אליה שוב מאוחר יותר יכולה רק להיות ארוכה יותר. לכן כל מילה נכנסת לתור פעם אחת, וברגע ש-endWord מופיעה כשכנה, המרחק שלה הוא התשובה.
הגרסה הזו מוצאת את השכנות של מילה על ידי השוואתה לכל מילה ברשימה, אות אחר אות, ועצירה בהבדל השני. כל אחת מעד n המילים שיוצאות מהתור דורשת n השוואות של עד L אותיות, כלומר O(n² × L) בסך הכול. עם 5,000 מילים וחיפוש שמבקר ברובן, מדובר בעד 25 מיליון השוואות בין מילים. שפה מקומפלת מבצעת זאת במהירות, אבל Python זקוקה לכמה שניות במבחן הגדול ביותר.
אלגוריתם
- אם
endWordלא נמצא ב-wordList, החזר 0. - הוסף את
beginWordלתור באורך 1. סמן אותו ככזה שבוקר אם הוא נמצא ברשימה. - קח את המילה הבאה ואת האורך שלה מהתור.
- השווה אותה לכל מילה שלא בוקרה ברשימה. עבור כל מילה שנבדלת ממנה באות אחת בדיוק: אם היא
endWord, החזר אורך + 1; אחרת סמן אותה ככזו שבוקרה והוסף אותה באורך + 1. - אם התור מתרוקן, אי אפשר להגיע אל
endWord: החזר 0.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
def one_letter_apart(a, b):
differences = 0
for x, y in zip(a, b):
if x != y:
differences += 1
if differences > 1:
return False
return differences == 1
if endWord not in wordList:
return 0
visited = [word == beginWord for word in wordList]
queue = deque([(beginWord, 1)]) # (word, words in the sequence up to it)
while queue:
word, length = queue.popleft()
# Compare against every word to find the neighbours.
for i, candidate in enumerate(wordList):
if not visited[i] and one_letter_apart(word, candidate):
if candidate == endWord:
return length + 1
visited[i] = True
queue.append((candidate, length + 1))
return 0חיפוש לרוחב עם דליי תווים כלליים
האינטואיציה
שומרים על חיפוש לרוחב, והופכים את מציאת השכנים לזולה. שתי מילים שונות באות אחת בדיוק כאשר הסתרת אותה מיקום בשתיהן הופכת אותן לשוות: hot ו־hit הופכות שתיהן ל־h*t. לכן, יוצרים לכל מילה L תבניות, אחת לכל מיקום מוסתר, ומוסיפים את המילה לדלי עבור כל תבנית. השכנים של מילה הם שאר המילים בדליי ה־L שלה, שאותם מוצאים באמצעות L חיפושי גיבוב במקום לעבור על הרשימה כולה.
כך נראה החיפוש בדוגמה הראשונה. התבניות של lead הן *ead, l*ad, le*d ו־lea*. הדלי l*ad מכיל את load, והדלי le*d מכיל את lend ואת lewd, ולכן רמה 2 כוללת את שלוש המילים האלה. מתוך load, הדלי *oad נותן את goad ברמה 3, ומתוך goad, התבנית go*d נותנת את gold ברמה 4.
חיסכון נוסף: לאחר שסרקנו את הדלי של מילה, הגענו לכל מילה שנמצאת בו, ולכן מרוקנים אותו. מילים מאוחרות יותר שחולקות את התבנית ממילא לא ימצאו בו שום דבר חדש. בבדיקה שבה aaa, baa עד zaa חולקות את *aa, סורקים את הדלי הזה, שמכיל 26 מילים, פעם אחת במקום 26 פעמים. כך החיפוש עובר על כל אחת מרשומות הדליים n × L לכל היותר פעם אחת.
בניית התבניות דורשת n × L מחרוזות באורך L אותיות, זמן ומקום של O(n × L²), וגם החיפוש עולה אותו הדבר: כל מילה שיוצאת מהתור בונה מחדש את L התבניות שלה. עבור 5,000 מילים בנות 10 אותיות, מדובר בכ־500,000 צעדי אותיות, לעומת עד 250 מיליון בהשוואה זוגית.
אלגוריתם
- אם
endWordלא נמצא ב-wordList, החזר 0. - עבור כל מילה ברשימה, וגם עבור
beginWord, הוסף את המילה לדלי של כל אחת מתבניות ה-Lשלה. - התחל את התור עם
beginWord, סמן אותו ככזה שבוקר, וקבע את האורך ל-1. - עבד את התור רמה אחת בכל פעם. אם מילה היא
endWord, החזר את האורך. אחרת, עבור כל אחת מהתבניות שלה, הוסף לרמה הבאה כל מילה שלא בוקרה בדלי הזה, סמן אותה ככזו שבוקרה ורוקן את הדלי. - אחרי כל רמה, הוסף 1 לאורך. אם התור מתרוקן, החזר 0.
from collections import defaultdict, deque
def ladderLength(beginWord, endWord, wordList):
if endWord not in wordList:
return 0
size = len(beginWord)
# "h*t" -> every word that matches it: hot, hat, hit... are one letter apart.
buckets = defaultdict(list)
for word in set(wordList) | {beginWord}:
for i in range(size):
buckets[word[:i] + "*" + word[i + 1:]].append(word)
visited = {beginWord}
queue = deque([beginWord])
length = 1 # words in the sequence up to the current level
while queue:
for _ in range(len(queue)): # one level: every word at this distance
word = queue.popleft()
if word == endWord:
return length
for i in range(size):
pattern = word[:i] + "*" + word[i + 1:]
for neighbour in buckets[pattern]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
buckets[pattern] = [] # all of them are visited now: never scan it again
length += 1
return 0
מלכודות ומקרי קצה
רוב התשובות השגויות נובעות מספירה של הדבר הלא נכון או מהכלל לגבי endWord.
- החזרת מספר השינויים במקום מספר המילים. המעבר מ־
leadל־goldדורש 3 שינויים ו־4 מילים, והתשובה היא 4. - אי־בדיקה ש־
endWordנמצא ב־wordList. בדוגמה השנייה, החיפוש מגיע לאות אחת מתוךdog, אבל התשובה היא 0. - שימוש בחיפוש לעומק (DFS) והחזרת השרשרת הראשונה שהוא מוצא. DFS ממשיך בענף אחד ככל האפשר, ולכן השרשרת הראשונה שלו ארוכה לעיתים קרובות.
- סימון מילה ככזו שכבר ביקרנו בה כשהיא יוצאת מהתור, במקום כשהיא מצטרפת אליו. מילה בדלי מלא של 26 מילים יכולה אז להצטרף לתור עד 25 פעמים, והתור גדל הרבה מעבר ל־
n. - השארת
beginWordללא סימון כשהיא מופיעה גם ב־wordList. החיפוש מגיע אליה שוב כעבור שתי רמות וחוזר על העבודה. סמנו אותה ככזו שכבר ביקרנו בה כבר מההתחלה. - בדיקה אם מילים שונות באות אחת לכל היותר. כל מילה שונה מעצמה באפס אותיות, ולכן התנאי הוא בדיוק אות אחת.
- רקורסיה לאורך השרשרת. בבדיקה חבויה אחת, השרשרת הקצרה ביותר מכילה 1,500 מילים, עומק רב מספיק כדי לגרום לגלישת מחסנית הקריאות בשפות מסוימות. BFS זקוק לתור בלבד.
שאלות נפוצות4
למה חיפוש לרוחב מוצא את סולם המילים הקצר ביותר?
BFS סורק את המילים בסבבים: תחילה את מילת ההתחלה, אחר כך כל מילה שנמצאת במרחק שינוי אחד, ואז כל מילה שנמצאת במרחק שני שינויים. מגיעים למילה בפעם הראשונה בסבב המוקדם ביותר שבו אפשר להגיע אליה, ולכן המרחק שלה הוא מספר השינויים הקטן ביותר האפשרי. זה עובד רק משום שכל שינוי נחשב באותה מידה. אם לכל צעד היו עלויות שונות, היה צורך להשתמש באלגוריתם של Dijkstra.
מהי סיבוכיות הזמן של Word Ladder?
עם דליי תווים כלליים, בניית התבניות והרצת החיפוש אורכות O(n × L²) עבור n מילים באורך L, מכיוון שלכל מילה יש L תבניות בנות L אותיות. השוואת כל זוג מילים עולה במקום זאת O(n² × L), וניסיון של כל סולם באמצעות חיפוש לעומק הוא מעריכי.
איך מוצאים מילים שנבדלות באות אחת?
דרך אחת היא דליי התווים הכלליים שלמעלה: מילים שחולקות תבנית כגון h*t הן שכנות. הדרך השנייה היא לשנות כל מיקום במילה לכל אחת מ־26 האותיות ולחפש את התוצאה בקבוצת גיבוב של המילים. זה דורש 26 × L חיפושים לכל מילה, כשכל אחד מגבב L אותיות, ולכן הסיבוכיות הכוללת היא O(n × 26 × L²). שתי השיטות עדיפות על השוואה לכל הרשימה.
האם BFS דו־כיווני יכול להאיץ את Word Ladder?
כן. חפשו בו-זמנית מ-beginWord ומ-endWord, והרחיבו בכל פעם את הצד הקטן יותר ברמה אחת, עד שמילה חדשה כבר הגיעה מהצד השני. הסולם כולל אז מילה אחת יותר ממספר השינויים שבוצעו בשני הצדדים יחד. אם לכל מילה יש בערך b שכנים והסולם דורש d שינויים, חיפוש אחד עשוי לעבור על כ-b^d מילים, בעוד ששני חיפושים שנפגשים באמצע עוברים על כ-2 × b^(d/2) מילים.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def ladderLength(beginWord, endWord, wordList):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
beginWord = "lead" endWord = "gold" wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
צפוי
4