Lunski's Clutter

This is a place to put my clutters, no matter you like it or not, welcome here.

0%

Trie

Posted on Edited on In
Symbols count in article: 5.7k Reading time ≈ 5 mins.

有序字典樹。

第一層到任意葉節點，都可以成為一個單字。

背景知識

物件導向

理解問題

實做字典樹，包含插入，搜尋，開頭功能。

思路視覺化

1
2
3
4
5
6
7
8
9
10
11
12
13
class Node:
  def __init__(self):
    self.children = {} # Key : letter
    self.end = False # finished or not
 class Trie:
    def __init__(self):
        self.root = Node()  
 def insert(self, word):
   逐一加入單字，新的字給一個新節點，移動到下個節點，並標示結尾
  def search(self, word):
    回傳是否有這個字
  def startsWith(self, prefix):  
    回傳字母有無在next

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.HashMap;
import java.util.Map;
class Trie {
    static class Node {
        private Map<Character, Node> children;
        private boolean end;

        public Node(boolean end) {
            this.end = end;
            this.children = new HashMap<>();
        }
    }
    private Node root;
    public Trie() {
        root = new Node(false);
    }

    public void insert(String word) {
        Node current = root;
        for (int i = 0; i < word.length(); ++i) {
            char ch = word.charAt(i);

            if (!current.children.containsKey(ch)) {
                current.children.put(ch, new Node(false));
            }

            current = current.children.get(ch);
            current.end = current.end | (i == word.length() - 1); // end of word, true
        }
    }

    public boolean search(String word) {
        Node current = root;
        for (int i = 0; i < word.length(); ++i) {
            char ch = word.charAt(i);
            current = current.children.get(ch);
            if (null == current) return false;
        }
        return current.end;
    }

    public boolean startsWith(String prefix) {
        Node current = root;
        for (int i = 0; i < prefix.length(); ++i) {
            char ch = prefix.charAt(i);
            current = current.children.get(ch);
            if (null == current) return false;
        }
        return true;
    }

}

class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));
        System.out.println(trie.search("app"));
        System.out.println(trie.startsWith("app"));
        trie.insert("app");
        System.out.println(trie.search("app"));
    }
}

>
java -cp /tmp/ZzMu196mR2 Main
true
false
true
true

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Node:
  def __init__(self):
    self.children = {} # Char : Node
    self.end = False # finished or not
    
class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word):
        current = self.root
        for letter in word:
            if letter not in current.children: # not child
                current.children[letter] = Node() # new node
            current = current.children[letter] # to child node
        current.end = True # leaf

    def search(self, word):
        current = self.root
        for letter in word:
            if letter not in current.children: 
                return False # not found
            else:
                current = current.children[letter] # to child node
        return current.end # found

    def startsWith(self, prefix):
        current = self.root
        for letter in prefix:
            if letter not in current.children:
                return False # not found
            else:
                current = current.children[letter] # to child node
        return True # found

trie = Trie()
trie.insert("apple")
print(trie.search("apple"))
print(trie.search("app"))
print(trie.startsWith('app'))
trie.insert('app')
print(trie.search('app'))

>
True
False
True
True

複雜度分析

TC:
O(n): insert, search, startsWith
SC:
O(n): insert
O(1): search, startsWith

Design a special dictionary that searches the words in it by a prefix and a suffix.

Implement the WordFilter class:

  • WordFilter(string[] words) Initializes the object with the words in the dictionary.
  • f(string pref, string suff) Returns the index of the word in the dictionary, which has the prefix pref and the suffix suff. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.

Example 1:

1
2
3
4
5
6
7
8
Input
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
Output
[null, 0]
Explanation
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = "e".

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
TC, SC: O(n*kˆ2)
import java.util.*;
class WordFilter {
    class Trie {
        class TrieNode {
            private TrieNode[] children;
            private List<Integer> indices; // index of current word
            public TrieNode() {
                children = new TrieNode[26];
                indices = new ArrayList<>();
            }
        }
        
        private TrieNode root;
        
        public Trie() {
            root = new TrieNode();
        }
        
        public void insert(String word, int i) {
            TrieNode cur = root;
            for (char c : word.toCharArray()) {
                int idx = c-'a'; // minus begin word, get char index
                cur.indices.add(i);
                // if no character
                if (cur.children[idx] == null) {
                    cur.children[idx] = new TrieNode();
                }
                cur = cur.children[idx]; // to next child
            }
            cur.indices.add(i); // add index
        }
        
        public List<Integer> find(String prefix) {
            TrieNode cur = root;
            for (char c : prefix.toCharArray()) {
                int idx = c-'a';
                if (cur.children[idx] == null) return new ArrayList<>();
                cur = cur.children[idx];
            }
            return cur.indices;
        }
    }   
    private Trie t;
    private String[] words;
    public WordFilter(String[] words) {
        t = new Trie();
        this.words = words;
        for (int i = 0; i < words.length; i++) {
            t.insert(words[i], i);
        }
    }
    
    // find word start with prexix and end with suffix, return index
    public int f(String prefix, String suffix) {
        List<Integer> l = t.find(prefix);
        for (int i = l.size()-1; i >= 0; i--) {
            if (words[l.get(i)].endsWith(suffix)) return l.get(i);
        }
        return -1;
    }
    public static void main(String[] args) {
        String[] str = {"apple"};
        WordFilter wordFilter = new WordFilter(str);
        System.out.println(wordFilter.f("a", "e"));
    }
}

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Welcome to my other publishing channels