البحث عن الكلمات II: Trie والتراجع على شبكة
أدرج جميع الكلمات المستهدفة في Trie، ونفّذ تراجعًا باستخدام DFS على رقعة ثنائية الأبعاد للعثور على جميع الكلمات الصالحة بالتزامن في O(m × n × 4^L).
البحث عن الكلمات II: Trie والتراجع على شبكة درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
مشكلة Word Search II
Word Search II (LeetCode 212): معطاة لوحة أحرف بحجم m × n وقائمة كلمات، أوجد جميع الكلمات التي يمكن تكوينها من خلايا متجاورة تباعًا (أفقيًا أو رأسيًا)، مع عدم السماح باستخدام كل خلية إلا مرة واحدة. هذه المسألة أصعب من Word Search I (كلمة واحدة)، لأننا نحتاج إلى العثور على جميع الكلمات المطابقة في الوقت نفسه؛ إذ إن تشغيل Word Search I لكل كلمة بطريقة ساذجة يحقق التعقيد O(W × m × n × 4^L)، وهو بطيء جدًا.
لماذا نستخدم Trie مع التراجع؟
يتيح إدراج جميع الكلمات المستهدفة في شجرة Trie ثم تشغيل DFS مع التراجع على اللوحة البحث عن جميع الكلمات في الوقت نفسه. في كل خلية من خلايا اللوحة، نتحقق بدلًا من السؤال «هل يشكل هذا المسار كلمتي المستهدفة؟» من السؤال «هل يطابق هذا المسار بادئة في شجرة Trie؟». وما إن تفشل بادئة في شجرة Trie حتى نشذّب فرع DFS بأكمله، ونتجنب بذلك العمل المتكرر بين جميع الكلمات التي تشترك في تلك البادئة.
إنشاء شجرة Trie من قائمة الكلمات
أدرج جميع الكلمات في شجرة Trie. خزّن الكلمة الكاملة في العقدة الورقية (في node.word) بدلًا من تخزين قيمة منطقية فقط، بحيث يمكننا عند العثور على تطابق كامل أثناء التراجع إضافة الكلمة فورًا إلى النتائج دون إعادة بنائها حرفًا حرفًا.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None # stores the complete word if this is an end node
def build_trie(words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word # mark complete word here
return root
root = build_trie(['eat','oath','ot'])
print('Trie built with', len(root.children), 'root children')التراجع باستخدام DFS على الشبكة
ابدأ DFS من كل خلية في اللوحة. في كل خطوة: (1) تحقق مما إذا كان حرف الخلية الحالية موجودًا كابن في عقدة Trie الحالية؛ (2) إذا كان موجودًا، علّم الخلية بأنها مستخدمة (اضبطها على قيمة حارسة مثل '#')، ثم نفّذ الاستدعاء التكراري على الجيران الأربعة؛ (3) بعد انتهاء الاستدعاء التكراري، استعد الخلية (أزل العلامة). عندما تحتوي عقدة Trie على قيمة غير None في word، أضفها إلى النتائج واضبطها على None لتجنب التكرارات.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None # avoid duplicates
board[i][j] = '#' # mark visited
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, next_node)
board[i][j] = c # restore
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result
board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']]
words = ['oath','pea','eat','rain']
print(findWords(board, words)) # ['oath','eat']تحليل التعقيد
الزمن: O(m × n × 4^L) حيث إن L هو أقصى طول للكلمات. بالنسبة إلى كل خلية بداية من m×n، يستكشف DFS ما يصل إلى 4^L من المسارات. تشذّب شجرة Trie المسارات التي لا تطابق أي بادئة لكلمة، لذلك يكون التنفيذ أسرع بكثير عمليًا. يستغرق إنشاء شجرة Trie وقتًا قدره O(W × L)، حيث إن W هو عدد الكلمات. المساحة: O(W × L) لشجرة Trie، بالإضافة إلى عمق مكدس الاستدعاء التكراري O(L).
التشذيب: إزالة العقد الورقية بعد العثور على كلمة
بعد العثور على كلمة، أزل العقدة الورقية من شجرة Trie (ولا تكتفِ بضبط الكلمة على قيمة فارغة) إذا لم تكن لها أبناء. يمنع ذلك إعادة زيارة الفروع الميتة في استدعاءات DFS اللاحقة. وعندما تصبح أبناء عقدة ما فارغة بعد العثور على الكلمة، أزلها من قاموس أبناء والدها. يكون هذا التحسين مهمًا عندما تشترك كلمات كثيرة في بادئات طويلة.
def dfs_with_pruning(i, j, node, board, m, n, result):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs_with_pruning(ni, nj, next_node, board, m, n, result)
board[i][j] = c
# Prune: if the node has no more children and no word, remove it
if not next_node.children and not next_node.word:
del node.children[c]
print('Leaf pruning removes exhausted trie branches during search')لماذا يُعد تخزين word في العقدة أفضل
يوفر تخزين الكلمة الكاملة في العقدة الورقية لشجرة Trie (بدلًا من إعادة بنائها من مسار DFS) ميزتين: (1) استرجاع الكلمة في O(1) عند العثور على تطابق بدلًا من إعادة بناء المسار في O(L)؛ (2) ضبط node.word = None بعد العثور على الكلمة يوفر إزالة تكرار نظيفة في O(1) دون الحاجة إلى مجموعة نتائج منفصلة. ويُعد منع التكرارات مهمًا خصوصًا في Word Search II، لأن الكلمة نفسها يمكن نظريًا العثور عليها عبر مسارات مختلفة.
وضع علامة على الخلايا المستخدمة داخل اللوحة
بدلًا من استخدام مجموعة visited منفصلة (التي تتطلب مساحة O(m × n) لكل مسار DFS)، نضع علامة على الخلايا داخل اللوحة باستبدال حرفها بقيمة حارسة مثل '#'. وبعد عودة DFS، نستعيد الحرف الأصلي. تحقق هذه التقنية ما يلي: (1) تستخدم مساحة إضافية قدرها O(1) لكل خلية؛ (2) تمنع تلقائيًا إعادة الزيارة ضمن المسار الواحد؛ (3) لا تؤثر إطلاقًا في اجتياز شجرة Trie، لأن '#' لن يوجد فيها.
الحالات الطرفية التي يجب معالجتها
الحالات الطرفية المهمة: (1) الكلمات المكررة في قائمة الكلمات — خزّن الكلمات في مجموعة، أو استخدم الحيلة node.word = None لمنع التكرارات في النتائج؛ (2) الكلمات الطويلة جدًا التي تتجاوز أبعاد اللوحة — لا يمكن تكوينها، لكن DFS يعالج ذلك طبيعيًا عند نفاد الخلايا المتجاورة؛ (3) لوحة من خلية واحدة — لا يمكن العثور إلا على كلمات من حرف واحد؛ (4) إمكانية العثور على الكلمة نفسها عبر مسارات مختلفة — تمنع حيلة node.word = None احتسابها مرتين.
مقارنة بالأسلوب الساذج
الأسلوب الساذج: بالنسبة إلى كل كلمة من W كلمات، شغّل Word Search I، بتعقيد O(W × m × n × 4^L). أما باستخدام شجرة Trie، فتُبحث جميع الكلمات في الوقت نفسه، بتعقيد O(m × n × 4^L) بغض النظر عن W. بالنسبة إلى W=1000 كلمة طول كل منها 10 على لوحة بحجم 10×10، يكون الأسلوب الساذج أبطأ بمقدار 1000 مرة من شجرة Trie. تعمل شجرة Trie كمرشح بادئات مشترك يوزع التكلفة بين جميع الكلمات، وهذا مثال تقليدي على استخدام بنية بيانات لتحقيق تحسن تقاربي.
ملخص الحل الكامل
حل Word Search II الكامل: أنشئ شجرة Trie بالكلمات، وخزّن سلسلة الكلمة في العقدة الورقية. بالنسبة إلى كل خلية في اللوحة، شغّل DFS: تحقق مما إذا كان الحرف الحالي موجودًا في عقدة Trie الحالية، واضبط الخلية على '#'، ثم نفّذ الاستدعاء التكراري على الجيران الأربعة، وبعدها استعد الخلية. عندما تكون قيمة node.word غير فارغة، أضف الكلمة إلى النتائج واضبطها على قيمة فارغة. ويمكن اختياريًا تشذيب فروع شجرة Trie الفارغة بعد استخدامها. أعد قائمة النتائج. الزمن: O(m×n×4^L)، والمساحة: شجرة Trie بحجم O(W×L) بالإضافة إلى تكرار بعمق O(L).
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords_final(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
node = node.children.setdefault(c, TrieNode())
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
child = node.children.get(c)
if not child:
return
if child.word:
result.append(child.word)
child.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, child)
board[i][j] = c
if not child.children:
del node.children[c]
for i in range(m):
for j in range(n):
dfs(i, j, root)
return resultتحقق سريع
اختبر مدى فهمك لمفاهيم Data Structures & Algorithms — Coding Interview Prep التي تناولها هذا الدرس.
مراجعة الدرس
تعلمت في هذا الدرس أن: Word Search II تستخدم شجرة Trie لتمكين البحث المتزامن عن كلمات متعددة مع تشذيب البادئات المشتركة، وأن تخزين سلسلة الكلمة في العقدة الورقية لشجرة Trie يتيح استرجاع الكلمة في O(1) وإزالة التكرارات بسهولة عبر ضبطها على None بعد العثور عليها، وأن وضع علامة على الخلايا المستخدمة داخل اللوحة باستخدام '#' يتجنب المساحة الإضافية O(m×n) لكل مسار DFS. بهذا يكتمل مقرر Tries and String Algorithms — لقد أتقنت إحدى أقوى هياكل البيانات المتخصصة في السلاسل النصية والمستخدمة في المقابلات.
الأسئلة الشائعة
هل درس «البحث عن الكلمات II: Trie والتراجع على شبكة» مجاني؟
نعم — نص درس «البحث عن الكلمات II: Trie والتراجع على شبكة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «البحث عن الكلمات II: Trie والتراجع على شبكة»؟
أدرج جميع الكلمات المستهدفة في Trie، ونفّذ تراجعًا باستخدام DFS على رقعة ثنائية الأبعاد للعثور على جميع الكلمات الصالحة بالتزامن في O(m × n × 4^L). تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «البحث عن الكلمات II: Trie والتراجع على شبكة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- الفئة TrieNode: الإدراج والبحث
- البحث عن البادئات وStarts-With
- البحث باستخدام الرموز البديلة والتعبيرات النمطية في Trie
- البحث عن الكلمات II: Trie والتراجع على شبكة