Implement Trie (Prefix Tree)

Q: למה להשתמש בטרי במקום בקבוצת גיבוב?

קבוצת גיבוב מוצאת מילים שלמות ב־ O(L) , אבל אינה יכולה לענות על שאלה לגבי קידומת בלי לסרוק כל מילה. אחסון של כל קידומת בקבוצה שנייה עולה 210 אותיות עבור מילה אחת בת 20 אותיות. trie מאחסן כל קידומת משותפת פעם אחת ועונה על שתי השאלות במעבר אחד.

בינוניעץ תחיליות

+10

בנו עץ טריי (עץ קידומות) עבור מילים באותיות קטנות עם שלוש פעולות: 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

עץ trie: קישורים לצמתים ילדים ודגל סיום

האינטואיציה

כל צומת מייצג קידומת אחת — האותיות שבנתיב מהשורש אליו. הוא מכיל קישור לצומת בן עבור כל אות שיכולה לבוא בהמשך (26 מקומות או מפה), ודגל isEnd שמציין אם מילה שמורה מסתיימת בדיוק שם. הוספת tea יוצרת את הצמתים עבור t, te ו-tea; הוספת ten לאחר מכן מוסיפה רק את ten, כי שתי המילים חולקות את הנתיב עבור te.

מעבר שנתקל בקישור חסר מוכיח שאף מילה שמורה לא מתחילה באותיות האלה: tex נעצר ב-te, שאין לו קישור ל-x. מעבר שמגיע לסוף עומד בצומת של השאילתה, ולכן startsWith הוא true ו-search מחזיר את ערך הדגל. הצומת של te קיים, אך הדגל שלו כבוי, ולכן search te הוא false. כל פעולה עוברת לכל היותר על L קישורים, בלי קשר למספר המילים השמורות, והטרייה מכילה צומת אחד לכל קידומת ייחודית.

אלגוריתם

צרו שורש ללא קישורי ילדים, כאשר isEnd כבוי.
insert w: מהשורש, עקבו אחר הקישור של כל אות, וצרו צומת אם הוא חסר. הפעילו את isEnd בצומת האחרון.
find(p): מהשורש, עקבו אחר הקישור של כל אות; החזירו דבר אם אחד מהם חסר, אחרת החזירו את הצומת שאליו הגעתם.
search w: אמת כאשר find(w) מחזירה צומת שבו isEnd מופעל.
startsWith p: אמת כאשר 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

מהי סיבוכיות הזמן של trie?

הוספה, חיפוש ו־startsWith עוברים כל אחד לאורך קישור אחד לכל אות, ולכן כל אחד מהם דורש O(L) עבור מילה באורך L, בלי קשר למספר המילים המאוחסנות. המקום הנדרש הוא O(T) צמתים עבור T אותיות שהוכנסו בסך הכול, כאשר כל צומת מכיל עד 26 קישורים לילדים.

למה להשתמש בטרי במקום בקבוצת גיבוב?

קבוצת גיבוב מוצאת מילים שלמות ב־O(L), אבל אינה יכולה לענות על שאלה לגבי קידומת בלי לסרוק כל מילה. אחסון של כל קידומת בקבוצה שנייה עולה 210 אותיות עבור מילה אחת בת 20 אותיות. trie מאחסן כל קידומת משותפת פעם אחת ועונה על שתי השאלות במעבר אחד.

האם צומת בטרייה צריך להשתמש במערך של 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"]