البحث باستخدام الرموز البديلة والتعبيرات النمطية في Trie
ادعم مطابقة الرمز البديل '.' عبر التفرّع إلى جميع الأبناء في ذلك العمق، وحلّ مسألة بنية البيانات design-add-and-search-words.
البحث باستخدام الرموز البديلة والتعبيرات النمطية في Trie درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
مشكلة البحث باستخدام أحرف البدل
يتعامل البحث القياسي في شجرة Trie مع الأحرف المطابقة تمامًا. يضيف البحث باستخدام أحرف البدل حرفًا خاصًا '.' يطابق أي حرف واحد. عند مواجهة '.' أثناء البحث، يجب بدلًا من اتباع ابن محدد واحد تجربة جميع الأبناء، وهذا ما يُسمى التفرع. هذه هي الفكرة الأساسية وراء مسألة LeetCode 211 'Design Add and Search Words Data Structure'. يضاعف كل '.' عدد مسارات البحث بعدد الأبناء في ذلك المستوى.
البحث التكراري باستخدام أحرف البدل
نفّذ البحث باستخدام أحرف البدل من خلال دالة مساعدة تكرارية تستخدم DFS. بالنسبة إلى كل حرف في النمط: إذا كان حرفًا حرفيًا، فاتبع الابن المحدد (أو أعد False إذا لم يكن موجودًا)؛ وإذا كان '.'، فاستدعِ الدالة تكراريًا لجميع الأبناء وأعد True إذا نجح أي منها. عند الوصول إلى نهاية النمط، أعد node.is_end.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return node.is_end
c = word[i]
if c == '.':
return any(dfs(child, i+1) for child in node.children.values())
if c not in node.children:
return False
return dfs(node.children[c], i+1)
return dfs(self.root, 0)
wd = WordDictionary()
wd.addWord('bad')
wd.addWord('dad')
wd.addWord('mad')
print(wd.search('.ad')) # True
print(wd.search('b..')) # True
print(wd.search('pad')) # Falseلماذا نستخدم any() للتفرع
عند مواجهة '.'، نستدعي any(dfs(child, i+1) for child in node.children.values()). مولّد any() يستخدم التقييم القصير؛ إذ يتوقف فورًا عندما يعيد أحد الأبناء True. ويجنبنا ذلك الاستكشاف غير الضروري. في أسوأ الحالات (عندما يتكون النمط بالكامل من '.')، نستكشف جميع المسارات، ويكون التعقيد O(26^k) حيث إن k هو عدد النقاط، مما يجعل أنماطًا مثل '....' مكلفة في أشجار Trie الكبيرة.
البحث التكراري باستخدام أحرف البدل والطوابير
يستخدم الأسلوب التكراري طابورًا من الأزواج (node, index). ابدأ بالزوج (root, 0). بالنسبة إلى كل زوج، إذا كان index == len(word) وكانت قيمة node.is_end صحيحة، فأعد True. وإلا، عالج الحرف الحالي: بالنسبة إلى '.'، أضف جميع الأبناء إلى الطابور؛ وبالنسبة إلى حرف حرفي، أضف الابن المطابق فقط. هذا في جوهره تطبيق لـ BFS على مسارات شجرة Trie.
from collections import deque
def search_iterative(root, word):
queue = deque([(root, 0)])
while queue:
node, i = queue.popleft()
if i == len(word):
if node.is_end:
return True
continue
c = word[i]
if c == '.':
for child in node.children.values():
queue.append((child, i+1))
elif c in node.children:
queue.append((node.children[c], i+1))
return False
print('Iterative BFS-based wildcard search')تحليل تعقيد البحث باستخدام أحرف البدل
عندما لا يحتوي النمط على أحرف بدل، يكون البحث في O(m). أما النمط الذي يحتوي على k من أحرف البدل، فأسوأ تعقيد له هو O(26^k × m)، أي أُسّي بالنسبة إلى عدد أحرف البدل. عمليًا، تكون أحرف البدل متناثرة عادةً وتكون شجرة Trie ضحلة، لذا يكون الأداء مقبولًا. أما الأنماط المكوّنة بالكامل من أحرف البدل (مثل مطابقة جميع الكلمات ذات الطول k)، فتتحول إلى اجتياز كامل لشجرة Trie.
البحث بالتعبيرات النمطية بعد أحرف البدل المفردة
يتطلب التوسّع إلى التعبيرات النمطية الكاملة (مثل '*' الذي يطابق صفرًا أو أكثر من الأحرف) معالجة مختلفة. يمكن لـ '*' مطابقة أي لاحقة، لذلك عند مواجهته يجب تجربة جميع مسارات شجرة Trie بدءًا من العقدة الحالية. إن المطابقة الفعلية للتعبيرات النمطية في شجرة Trie معقدة، وعادةً ما تُترك لإنشاءات NFA/DFA. في المقابلات، يكون نمط أحرف البدل المفردة ('.') هو النمط القياسي.
مطابقة أنماط Glob
يمكن تنفيذ مطابقة Glob باستخدام '?' (أي حرف واحد) و'*' (أي تسلسل، بما في ذلك التسلسل الفارغ) بواسطة البرمجة الديناميكية. وإذا نُفذت داخل شجرة Trie، فإن '?' يقابل التفرع على مستوى واحد (مثل '.')، بينما يقابل '*' اجتياز DFS متعدد المستويات. ويكون أسلوب البرمجة الديناميكية المدمج كما يلي: dp[i][j] = True إذا كان pattern[0..i] يطابق string[0..j]. وعادةً ما يحدد المحاور في المقابلة الصيغة المطلوب تنفيذها.
تطبيق عملي: توجيه عناوين IP
تُستخدم أشجار Trie التي تدعم أحرف البدل في جداول توجيه IP، حيث يعمل '*' كحرف بدل للبادئة. يخزّن الموجّه بادئات مسارات مثل '192.168.*' ويطابق العناوين الواردة. ويُنفّذ البحث عن أطول بادئة (أي يفوز المسار الأكثر تحديدًا) عبر اجتياز شجرة Trie إلى أعمق مستوى ممكن واستخدام آخر تطابق تم العثور عليه. هذا تطبيق واقعي لعمليات البادئات وأحرف البدل في شجرة Trie.
تحسين: تشذيب الفروع الميتة
عندما لا تحتوي عقدة في شجرة Trie على أبناء (أي تكون ورقة) وتكون قيمة is_end = False، فإن أي بحث يصل إليها سيعيد False. أثناء البحث باستخدام أحرف البدل، يمكن أن يؤدي تخطي هذه العقد النهائية الميتة قبل الاستدعاء التكراري إلى تشذيب الاستدعاءات غير الضرورية. كما يتيح الاحتفاظ بقيمة word_count في كل عقدة (إجمالي الكلمات في الشجرة الفرعية) تخطي شجرة فرعية كاملة إذا لم تطابق أي كلمات قيود طول النمط المتبقية.
فئة WordDictionary الكاملة (جاهزة للمقابلات)
فئة WordDictionary نظيفة وجاهزة للمقابلات، تجمع بين الإدراج والبحث باستخدام حرف البدل النقطي في فئة واحدة. هذا هو التنفيذ المتوقع تحديدًا لمسألة LeetCode 211. ويكون البحث التكراري باستخدام any() ذي التقييم القصير موجزًا ويوضح بجلاء منطق التفرع للمحاورين.
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word):
node = self.root
for c in word:
node = node.setdefault(c, {})
node['#'] = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return '#' in node
if word[i] == '.':
return any(dfs(v, i+1) for k, v in node.items() if k != '#')
nxt = node.get(word[i])
return dfs(nxt, i+1) if nxt is not None else False
return dfs(self.root, 0)
wd = WordDictionary()
for w in ['at','and','an','add']:
wd.addWord(w)
print(wd.search('a.')) # True (at, an)
print(wd.search('.nd')) # True (and)
print(wd.search('...')) # True (and, add)
print(wd.search('x.')) # Falseاستخدام setdefault لإنشاء شجرة Trie مدمجة
تعيد dict.setdefault(key, default) القيمة المرتبطة بالمفتاح إذا كان موجودًا، وإلا فتُدرج القيمة الافتراضية وتعيدها. يؤدي استخدام node.setdefault(c, {}) في عملية الإدراج إلى إلغاء الحاجة إلى التحقق باستخدام if-else؛ إذ ينشئ قاموس الابن إذا لم يكن موجودًا ويعيده في كلتا الحالتين. يجعل ذلك عملية الإدراج اجتيازًا في سطر واحد: for c in word: node = node.setdefault(c, {}). هذا أسلوب نظيف وملائم لـ Python.
تحقق سريع
اختبر مدى فهمك لمفاهيم Data Structures & Algorithms — Coding Interview Prep التي تناولها هذا الدرس.
مراجعة الدرس
تعلمت في هذا الدرس أن: حرف البدل '.' يتطلب التفرع إلى جميع الأبناء في الموضع المطابق باستخدام DFS التكراري، وأن استخدام any() مع مولّد يوفر تقييمًا قصيرًا للإنهاء المبكر، وأن setdefault يتيح إدراجًا مدمجًا لشجرة Trie في سطر واحد. في الخطوة التالية، سنجمع بين شجرة Trie والتراجع لحل Word Search II، أي العثور على كلمات متعددة في الوقت نفسه على لوحة ثنائية الأبعاد.
الأسئلة الشائعة
هل درس «البحث باستخدام الرموز البديلة والتعبيرات النمطية في Trie» مجاني؟
نعم — نص درس «البحث باستخدام الرموز البديلة والتعبيرات النمطية في Trie» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «البحث باستخدام الرموز البديلة والتعبيرات النمطية في Trie»؟
ادعم مطابقة الرمز البديل '.' عبر التفرّع إلى جميع الأبناء في ذلك العمق، وحلّ مسألة بنية البيانات design-add-and-search-words. تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «البحث باستخدام الرموز البديلة والتعبيرات النمطية في Trie»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- الفئة TrieNode: الإدراج والبحث
- البحث عن البادئات وStarts-With
- البحث باستخدام الرموز البديلة والتعبيرات النمطية في Trie
- البحث عن الكلمات II: Trie والتراجع على شبكة