LeetCode之團滅字典樹相關話題

經典模闆題

LeetCode208實作 Trie(字首樹)

Trie（發音類似 "try"）或者說 字首樹 是一種樹形資料結構，用于高效地存儲和檢索字元串資料集中的鍵。這一資料結構有相當多的應用情景，例如自動補完和拼寫檢查。

請你實作 Trie 類：

• ​

  ​Trie()​

  ​ 初始化字首樹對象。
• ​

  ​void insert(String word)​

  ​​ 向字首樹中插入字元串 ​

  ​word​

  ​ 。
• ​

  ​boolean search(String word)​

  ​​ 如果字元串 ​

  ​word​

  ​​ 在字首樹中，傳回 ​

  ​true​

  ​​（即，在檢索之前已經插入）；否則，傳回 ​

  ​false​

  ​ 。
• ​

  ​boolean startsWith(String prefix)​

  ​​ 如果之前已經插入的字元串 ​

  ​word​

  ​​ 的字首之一為 ​

  ​prefix​

  ​​ ，傳回 ​

  ​true​

  ​​ ；否則，傳回 ​

  ​false​

  ​ 。

示例：

輸入

["Trie", "insert", "search", "search", "startsWith", "insert", "search"]

[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

輸出

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

解釋

Trie trie = new Trie();

trie.insert("apple");

trie.search("apple"); // 傳回 True

trie.search("app"); // 傳回 False

trie.startsWith("app"); // 傳回 True

trie.insert("app");

trie.search("app"); // 傳回 True

解題思路

想象以下，包含三個單詞 "sea","sells","she" 的 Trie 會長啥樣呢？

 定義類 Trie

class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
}      

插入

描述：向 Trie 中插入一個單詞 word

實作：這個操作和建構連結清單很像。首先從根結點的子結點開始與 word 第一個字元進行比對，一直比對到字首鍊上沒有對應的字元，這時開始不斷開辟新的結點，直到插入完 word 的最後一個字元，同時還要将最後一個結點isEnd = true;，表示它是一個單詞的末尾。

public void insert(String word) {
     Trie node = this;
     for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
      }
      node.isEnd = true;
}      

字首比對

描述：判斷 Trie 中是或有以 prefix 為字首的單詞

實作：和 search 操作類似，隻是不需要判斷最後一個字元結點的isEnd，因為既然能比對到最後一個字元，那後面一定有單詞是以它為字首的。

public boolean startsWith(String prefix) {
     return searchPrefix(prefix) != null;
}

private Trie searchPrefix(String prefix) {
     Trie node = this;
     for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
      }
     return node;
}      

 查找

描述：查找 Trie 中是否存在單詞 word

實作：從根結點的子結點開始，一直向下比對即可，如果出現結點值為空就傳回 false，如果比對到了最後一個字元，那我們隻需判斷 node.isEnd即可。

public boolean search(String word) {
     Trie node = searchPrefix(word);
     return node != null && node.isEnd;
}      

代碼實作

class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}      

相關拓展

LeetCode1233删除子檔案夾

你是一位系統管理者，手裡有一份檔案夾清單 ​

​folder​

​，你的任務是要删除該清單中的所有 子檔案夾，并以 任意順序 傳回剩下的檔案夾。

如果檔案夾 ​

​folder[i]​

​​ 位于另一個檔案夾 ​

​folder[j]​

​​ 下，那麼 ​

​folder[i]​

​​ 就是 ​

​folder[j]​

​ 的 子檔案夾 。

檔案夾的「路徑」是由一個或多個按以下格式串聯形成的字元串：'/'

• 例如，​

  ​"/leetcode"​

  ​​ 和 ​

  ​"/leetcode/problems"​

  ​​ 都是有效的路徑，而空字元串和 ​

  ​"/"​

  ​ 不是。

示例 1：

輸入：folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
輸出：["/a","/c/d","/c/f"]
解釋："/a/b/" 是 "/a" 的子檔案夾，而 "/c/d/e" 是 "/c/d" 的子檔案夾。      

示例 2：

輸入：folder = ["/a","/a/b/c","/a/b/d"]
輸出：["/a"]
解釋：檔案夾 "/a/b/c" 和 "/a/b/d/" 都會被删除，因為它們都是 "/a" 的子檔案夾。      

輸入: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
輸出: ["/a/b/c","/a/b/ca","/a/b/d"]      

解題思路

代碼實作

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Trie trie = new Trie();
        for (String i : folder) {
            trie.add(i);
        }
        List<String> ans = new ArrayList<>();
        for (String i : folder) {
            if (trie.ok(i)) {
                ans.add(i);
            }
        }
        return ans;
    }
}

class Trie {
    HashMap<String, Trie> child;
    boolean isEnd;
    
    public Trie() {
        this.child = new HashMap<>();
        this.isEnd = false;
    }

    public void add(String s) {
        Trie root = this;
        String[] arr = s.split("/");
        for (int i = 0; i < arr.length; i++) {
            if (!root.child.containsKey(arr[i])) {
                root.child.put(arr[i], new Trie());
            }
            root = root.child.get(arr[i]);
        }
        root.isEnd = true;
    }

    public boolean ok(String s) {
        Trie root = this;
        String[] arr = s.split("/");
        for (int i = 0; i < arr.length; i++) {
            root = root.child.get(arr[i]);
            //已有的路徑已經到達末位,但是要檢測的字元串還未到達末位,說明這是個子檔案夾需要删除
            if (i != arr.length - 1 && root.isEnd) {
                return false;
            }
        }
        return true;
    }
}