Word Search

Q: ما هو التعقيد الزمني للبحث عن الكلمات؟

أسوأ حالة هي 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) خارج الشبكة، أو تمت زيارته، أو لم يكن حرفه هو word[i].
إذا كان i هو الفهرس الأخير في word، فأعد true.
علّم (r, c) على أنه تمت زيارته، وجرّب الجيران الأربعة باستخدام 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

ما هو التعقيد الزمني للبحث عن الكلمات؟

أسوأ حالة هي 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