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 ≤ 10endWordوكل كلمة في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، وهو مسار من كلمة واحدة. ثم كل كلمة تبعد عنه حرفًا واحدًا، وهي مسارات من كلمتين. ثم كل كلمة جديدة تبعد حرفًا واحدًا عن تلك الكلمات، وهي مسارات من 3 كلمات، وهكذا. تحافظ قائمة الانتظار على هذا الترتيب: تخرج الكلمات منها وفق ترتيب انضمامها إليها، لذا تخرج كل الكلمات التي تبعد مسافة d قبل أي كلمة تبعد مسافة d + 1.
هذا الترتيب هو سبب كون أول مسار يجده البحث بعرض الشجرة أقصر مسار. عندما يُبلَغ عن كلمة لأول مرة على مسافة d، تكون كل كلمة أقرب من d قد استُكشفت بالفعل، لذا لو وُجد مسار أقصر إليها، لكان البحث قد بلغ الكلمة في وقت أبكر. وبالحجة نفسها، من الآمن وضع علامة «تمت زيارتها» على الكلمة فور انضمامها إلى قائمة الانتظار: فمسافتها أصبحت نهائية، والوصول إليها مرة أخرى لاحقًا لا يمكن أن يكون إلا عبر مسار أطول. لذا تنضم كل كلمة إلى قائمة الانتظار مرة واحدة، وبمجرد ظهور endWord ككلمة مجاورة، تكون مسافتها هي الإجابة.
يجد هذا الإصدار الكلمات المجاورة لكلمة ما بمقارنتها بكل كلمة في القائمة، حرفًا بحرف، والتوقف عند الاختلاف الثاني. تكلّف كل كلمة من بين ما يصل إلى n كلمة تخرج من قائمة الانتظار n مقارنات يصل طول كل منها إلى L حرفًا، أي O(n² × L) إجمالًا. مع 5,000 كلمة وبحث يزور معظمها، يصل ذلك إلى 25 مليون مقارنة بين الكلمات. تنجز لغة مُصرَّفة ذلك بسرعة، لكن Python تحتاج إلى عدة ثوانٍ في أكبر اختبار.
الخوارزمية
- إذا لم تكن
endWordموجودة فيwordList، فأعِد 0. - ضع
beginWordفي قائمة انتظار بطول 1. علِّمها بأنها زِيرت إذا كانت موجودة في القائمة. - خذ الكلمة التالية وطولها من قائمة الانتظار.
- قارنها بكل كلمة غير مُزارة في القائمة. لكل كلمة تختلف عنها بحرف واحد بالضبط: إذا كانت
endWord، فأعِد length + 1؛ وإلا فضع علامة على أنها زِيرت وأضِفها بطول length + 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. - استخدام البحث بالعمق أولًا وإرجاع أول سلسلة تحويلات يعثر عليها. يتبع البحث بالعمق أولًا فرعًا واحدًا إلى أبعد نقطة ممكنة، لذا غالبًا ما تكون أول سلسلة تحويلات يعثر عليها طويلة.
- وضع علامة على الكلمة على أنها زِيرت عند خروجها من قائمة الانتظار بدلًا من إدخالها فيها. عندها قد تُضاف كلمة في مجموعة كاملة تضم 26 كلمة إلى قائمة الانتظار حتى 25 مرة، وتنمو قائمة الانتظار لتتجاوز
nبكثير. - ترك
beginWordدون وضع علامة عليها إذا كانت موجودة أيضًا فيwordList. عندها يصل البحث إليها مرة أخرى بعد مستويين ويكرر العمل. ضع علامة عليها على أنها زِيرت منذ البداية. - التحقق مما إذا كانت الكلمات تختلف في حرف واحد على الأكثر. تختلف كل كلمة عن نفسها في صفر من الأحرف، لذا الشرط هو الاختلاف في حرف واحد بالضبط.
- استخدام الاستدعاء الذاتي على طول سلسلة التحويلات. يحتوي اختبار مخفي على أقصر سلسلة تحويلات مؤلفة من 1,500 كلمة، وهي طويلة بما يكفي لتجاوز سعة مكدس الاستدعاءات في بعض اللغات. لا يحتاج البحث بالعرض أولًا إلا إلى قائمة انتظار.
أسئلة شائعة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²). وكلتا الطريقتين أفضل من المقارنة بالقائمة كاملة.
هل يمكن أن تجعل عملية البحث بالعرض ثنائية الاتجاه مسألة سُلّم الكلمات أسرع؟
نعم. ابحث بدءًا من 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