字段树

• 主要用于字符串匹配

  
  
  image.png

实现 插入和查找时间复杂度均为o(m) m为键长

• leetcode 208

class TrieNode {
    HashMap<Character, TrieNode> node;

    boolean isEnd;

    public TrieNode() {
        this.node = new HashMap<Character, TrieNode>();
        this.isEnd = false;
    }
}

class Trie {
    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        this.root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode t = root;
        for (int i = 0; i < word.length(); i++) {
            Character c = word.charAt(i);
            if (!t.node.containsKey(c)) {
                t.node.put(c, new TrieNode());
            }
            t = t.node.get(c);
        }
        t.isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode t = root;
        for (int i = 0; i < word.length(); i++) {
            Character c = word.charAt(i);
            if (!t.node.containsKey(c)) {
                return false;
            }
            t = t.node.get(c);
        }
        return t.isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode t = root;
        for (int i = 0; i < prefix.length(); i++) {
            Character c = prefix.charAt(i);
            if (!t.node.containsKey(c)) {
                return false;
            }
            t = t.node.get(c);
        }
        return true;
    }
}

典型题

leetcode 1032

class TrieNode {
    HashMap<Character, TrieNode> node;

    boolean isEnd;

    public TrieNode() {
        this.node = new HashMap<Character, TrieNode>();
        this.isEnd = false;
    }
}

class TrieTree {
    private TrieNode root;

    public TrieTree() {
        this.root = new TrieNode();
    }

    public void insert(String words) {
        TrieNode t = root;
        for (int i = 0; i < words.length(); i++) {
            Character c = words.charAt(i);
            if (!t.node.containsKey(c)) {
                t.node.put(c, new TrieNode());
            }
            t = t.node.get(c);
        }
        t.isEnd = true;
    }

    public boolean search(String words) {
        TrieNode t = root;
        for (int i = 0; i < words.length(); i++) {
            Character c = words.charAt(i);
            if (!t.node.containsKey(c)) {
                return false;
            }
            t = t.node.get(c);
        }
        return t.isEnd;
    }

    public boolean startWith(String words) {
        TrieNode t = root;
        for (int i = 0; i < words.length(); i++) {
            Character c = words.charAt(i);
            if (!t.node.containsKey(c)) {
                return false;
            }
            t = t.node.get(c);
        }
        return true;
    }
}

class StreamChecker {
    private TrieTree trieTree;

    private StringBuilder sb;

    public StreamChecker(String[] words) {
        trieTree = new TrieTree();
        sb = new StringBuilder();
        for (String word : words) {
            trieTree.insert(new StringBuffer(word).reverse().toString());
        }
    }
    
    public boolean query(char letter) {
        sb.append(letter);
        int len = sb.length();
        for (int i = len - 1; i >= 0; i--) {
            String temp = new StringBuilder(sb.substring(i)).reverse().toString();
            if (!trieTree.startWith(temp)) {
                return false;
            }
            if (trieTree.search(temp)) {
                return true;
            }
        }
        return false;
    }
}

leetcode 820

class TrieNode {
    HashMap<Character, TrieNode> node;

    boolean isEnd;

    public TrieNode() {
        this.node = new HashMap<Character, TrieNode>();
        this.isEnd = false;
    }
}

class TrieTree {
    private TrieNode root;

    public TrieTree() {
        this.root = new TrieNode();
    }

    public void insert(String words) {
        TrieNode t = root;
        for (int i = 0; i < words.length(); i++) {
            Character c = words.charAt(i);
            if (!t.node.containsKey(c)) {
                t.node.put(c, new TrieNode());
            }
            t = t.node.get(c);
        }
        t.isEnd = true;
    }

    public boolean search(String words) {
        TrieNode t = root;
        for (int i = 0; i < words.length(); i++) {
            Character c = words.charAt(i);
            if (!t.node.containsKey(c)) {
                return false;
            }
            t = t.node.get(c);
        }
        return t.isEnd;
    }

    public boolean startWith(String words) {
        TrieNode t = root;
        for (int i = 0; i < words.length(); i++) {
            Character c = words.charAt(i);
            if (!t.node.containsKey(c)) {
                return false;
            }
            t = t.node.get(c);
        }
        return true;
    }
}

class Solution {
    public int minimumLengthEncoding(String[] words) {
        TrieTree tree = new TrieTree();
        int result = 0;
        Arrays.sort(words, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (o1.length() == o2.length()) {
                    return 0;
                }
                return o1.length() < o2.length() ? 1 : -1;
            }
        });
        for (String s : words) {
            String reverse = new StringBuilder(s).reverse().toString();
            if (tree.startWith(reverse)) {
                continue;
            }
            tree.insert(reverse);
            result += s.length() + 1;
        }
        return result;
    }
}