Implement Trie (Prefix Tree)

Q: لماذا نستخدم شجرة بادئة بدلًا من مجموعة تجزئة؟

تعثر مجموعة التجزئة على الكلمات الكاملة في O(L) ، لكنها لا تستطيع الإجابة عن سؤال البادئة من دون فحص كل كلمة. ويتطلب تخزين كل بادئة في مجموعة ثانية 210 أحرف لكلمة واحدة طولها 20 حرفًا. تخزّن شجرة البادئات كل بادئة مشتركة مرة واحدة، وتجيب عن كلا السؤالين بمسير واحد.

متوسطشجرة البادئات

+10

أنشئ شجرة بادئات (trie) للكلمات المكتوبة بأحرف صغيرة، تتضمن ثلاث عمليات: تضيف insert w الكلمة w، وتحدد search w ما إذا كانت w نفسها قد أُدرجت، وتحدد startsWith p ما إذا كانت هناك كلمة مُدرجة تبدأ بـ p. تُعدّ الكلمة بادئةً لنفسها.

العملية i هي ops[i] على words[i]. نفّذ العمليات بالترتيب على شجرة بادئات فارغة، وأعِد سلسلة واحدة لكل عملية: "null" للإدراج، أو "true" أو "false" لعملية بحث أو startsWith.

الدالة

trieOps(ops: string-array, words: string-array) → string-array

opsstring-array: العمليات، بالترتيب الذي تُنفَّذ به
wordsstring-array: الكلمة أو البادئة لكل عملية
تُرجعstring-array: إجابة واحدة لكل عملية، كنص

القيود

1 ≤ ops.length ≤ 2000
words.length == ops.length
كل قيمة من ops[i] هي insert أو search أو startsWith.
1 ≤ words[i].length ≤ 20
words[i] لا يحتوي إلا على أحرف إنجليزية صغيرة.

أمثلة

المدخلات: ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
المخرجات: ["null", "false", "true", "null", "true"]
الشرح: car يبدأ بـ card، لذا فإن startsWith car هي "true"، لكن car لم يُدرج قط، لذا فإن البحث الأول هو "false". بعد insert car، يعثر البحث عليه.

المدخلات: ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
المخرجات: ["null", "null", "true", "false", "false", "true", "true"]
الشرح: تبدأ كلتا الكلمتين بـ te، لكن لا تساوي أيٌّ منهما te تمامًا، لذا تكون startsWith هي "true" ويكون البحث "false". لا تبدأ أي كلمة بـ tex، وtea بادئة لنفسها.

المدخلات: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
المخرجات: ["false", "false", "null", "true", "false", "true"]
الشرح: في شجرة البادئات الفارغة، تكون نتيجة كلا الاستعلامين "false". بعد insert dog، يعثر البحث عليه، ولا تبدأ أي كلمة بـ dogs، ويبدأ do كلمة dog.

سؤال إضافي

كيف ستضيف عملية countPrefix p تُعيد عدد الكلمات المخزنة المتميزة التي تبدأ بـ p، مع الحفاظ على زمن تنفيذ O(L)؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

تجيب مجموعة التجزئة عن search، لكنها لا تعرف شيئًا عن البدايات، لذا فإن startsWith سيمسح كل كلمة. تخزّن شجرة البادئات كل كلمة على هيئة مسار من الحروف يبدأ من الجذر: الكلمات التي تبدأ بالطريقة نفسها تتشارك مسارًا، وتحدّد علامةٌ الموضع الذي تنتهي عنده الكلمة المخزّنة. يصبح كلا الاستعلامين جولةً واحدةً لا تتجاوز L روابط.

احتفِظ بقائمة من الكلمات وافحصها

الفكرة

احتفِظ بكل كلمة مُدرجة في قائمة. تقارن search w بين w وكل كلمة مخزّنة، وتتحقق startsWith p مما إذا كانت أي كلمة مخزّنة تبدأ بـ p. وهذا صحيح لأنه يختبر التعريف مباشرةً. عند تخزين n كلمة، تتطلب كل عملية بحث ما يصل إلى n مقارنةً لما يصل إلى L حرفًا: 1,000 كلمة و1,000 عملية بحث تُنتج مليون مقارنة بين السلاسل النصية.

الخوارزمية

ابدأ بقائمة فارغة.
insert w: أضف w إلى النهاية.
search w: أعد ما إذا كانت هناك كلمة مخزنة تساوي w.
startsWith p: أعد ما إذا كانت هناك كلمة مخزنة تبدأ بـ p.

def trieOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            stored.append(word)
            result.append("null")
        elif op == "search":
            found = any(s == word for s in stored)
            result.append("true" if found else "false")
        else:
            found = any(s.startswith(word) for s in stored)
            result.append("true" if found else "false")
    return result

شجرة بادئة: روابط الأبناء وعلامة النهاية

الفكرة

تمثل كل عقدة بادئة واحدة، أي الحروف على المسار من الجذر إليها. وتحتوي على رابط ابن لكل حرف يمكن أن يأتي بعدها (26 خانة أو خريطة)، وعلى علامة isEnd تشير إلى ما إذا كانت كلمة مخزنة تنتهي عندها بالضبط. يؤدي إدراج tea إلى إنشاء العقد الخاصة بـ t وte وtea؛ ثم يؤدي إدراج ten إلى إضافة ten فقط، لأن الكلمتين تشتركان في المسار الخاص بـ te.

إن المسير الذي يصادف رابطًا مفقودًا يثبت أن لا كلمة مخزنة تبدأ بتلك الحروف: يتوقف tex عند te، التي لا تحتوي على رابط لـ x. أما المسير الذي يصل إلى النهاية فيقف عند العقدة الخاصة بالاستعلام، لذا تكون startsWith صحيحة، وتجيب search باستخدام العلامة. توجد العقدة الخاصة بـ te، لكن علامتها غير مفعّلة، لذا فإن search te تعيد false. تتبع كل عملية بحد أقصى L من الروابط، مهما كان عدد الكلمات المخزنة، وتحتوي شجرة البادئات على عقدة واحدة لكل بادئة مميزة.

الخوارزمية

أنشئ جذرًا بلا روابط أبناء واجعل isEnd متوقفًا.
insert w: من الجذر، اتبع الرابط الخاص بكل حرف، وأنشئ العقدة إذا لم تكن موجودة. عيّن isEnd في العقدة الأخيرة.
find(p): من الجذر، اتبع الرابط الخاص بكل حرف؛ وأعِد لا شيء فورًا إذا كان أحدها مفقودًا، وإلا فأعِد العقدة التي وصلت إليها.
search w: تكون النتيجة true عندما تعيد find(w) عقدةً تم تعيين isEnd فيها.
startsWith p: تكون النتيجة true عندما تعيد find(p) عقدةً.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> TrieNode
        self.is_end = False  # does a stored word end at this node?


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def _find(self, prefix):
        # Follow the letters from the root; None as soon as a link is missing.
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None


def trieOps(ops, words):
    trie = Trie()
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            trie.insert(word)
            result.append("null")
        elif op == "search":
            result.append("true" if trie.search(word) else "false")
        else:
            result.append("true" if trie.starts_with(word) else "false")
    return result

أخطاء شائعة وحالات حدّية

السماح لـ search بإرجاع true كلما كان المسار موجودًا. بعد insert card، يكون المسار الخاص بـ car موجودًا، لكن يجب أن تكون نتيجة search car هي false.
تعيين isEnd على العقد التي أُنشئت حديثًا فقط. إن إدراج card بعد cards لا ينشئ شيئًا، لكن العقدة الأخيرة تحتاج إلى علامتها.
إنشاء عقدة فرعية جديدة عندما يكون الرابط موجودًا بالفعل. يؤدي إدراج ten مع عقدة t جديدة إلى فقدان tea.
المتابعة بعد نهاية المسار. يجب أن يتوقف startsWith sunny، مع تخزين sun فقط، عند أول رابط مفقود ويُرجع false.

أسئلة شائعة3

ما هو التعقيد الزمني لشجرة البادئات؟

يتبع كل من الإدراج والبحث وstartsWith رابطًا واحدًا لكل حرف، لذا يستغرق كل منها O(L) لكلمة طولها L، مهما كان عدد الكلمات المخزنة. تبلغ المساحة O(T) عقدًا مقابل T أحرف مُدرجة إجمالًا، وتحتوي كل عقدة على ما يصل إلى 26 رابطًا فرعيًا.

لماذا نستخدم شجرة بادئة بدلًا من مجموعة تجزئة؟

تعثر مجموعة التجزئة على الكلمات الكاملة في O(L)، لكنها لا تستطيع الإجابة عن سؤال البادئة من دون فحص كل كلمة. ويتطلب تخزين كل بادئة في مجموعة ثانية 210 أحرف لكلمة واحدة طولها 20 حرفًا. تخزّن شجرة البادئات كل بادئة مشتركة مرة واحدة، وتجيب عن كلا السؤالين بمسير واحد.

هل ينبغي لعقدة في شجرة البادئات أن تستخدم مصفوفة من 26 رابطًا أم خريطة تجزئة؟

تصل المصفوفة إلى الابن باستخدام فهرس واحد، لكنها تستهلك 26 خانة لكل عقدة، حتى لو كان للعقدة ابن واحد فقط. أما الخريطة فتخزّن الأبناء الموجودين فقط، وتعمل مع أي أبجدية، مقابل تكلفة تجزئة لكل حرف. بالنسبة إلى الأحرف الإنجليزية الصغيرة، كلاهما مناسب؛ أما في حالة Unicode أو أشجار البادئات المتفرقة، فتوفّر الخريطة الذاكرة.

def trieOps(ops, words):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

ops = ["insert", "search", "startsWith", "insert", "search"]
words = ["card", "car", "car", "car", "car"]

الإخراج المتوقع

["null", "false", "true", "null", "true"]