前缀树/Trie

概述

Trie 也加字典树，它是一个树形结构。它主要用于处理字符串匹配的数据结构。此外Trie 树也称 前缀树（PrfixTree），主要判断字符串是否是以某个子串开头。

用途

解决在一组字符串集合中快速查找某个字符串的问题。

性质

每个节点至少包含两个基本属性
child:数组或者集合，罗列出每个分支当中包含的所有字符
isEnd 布尔值表示该节点是否为某个字符串的结尾

操作

创建

遍历一遍输入的字符串，对每个字符串的字符进行遍历
从前缀树的根节点开始，将每个字符加入到节点的children字符集当中
如果字符集已经包含了这个字符，跳过
如果当前字符是字符串的最后一个，把当前节点的isEnd标记为真

import java.util.TreeMap;
public class Trie {
    private class Node{
        public boolean isWord;
        public TreeMap<Character,Node> next;
        public Node(boolean isWord) {
            this.isWord = isWord;
            next = new TreeMap<>();
        }
    }
    private Node root;
    private int size;
    public Trie(){
        root = new Node(false);
        size = 0;
    }
    public void add(String word){
        Node currNode = root;
        for(int i = 0;i<word.length();i++){
            char c = word.charAt(i);
            if (currNode.next.get(c) ==null){
                currNode.next.put(c,new Node(false));
            }
            currNode = currNode.next.get(c);
        }
        if (!currNode.isWord){
            currNode.isWord = true;
            size++;
        }
    }
}

一个 int 即可存储 26 个字母

class Trie {
    class TrieNode {
        private int v;
        boolean end;
        TrieNode[] next = new TrieNode[26];
        TrieNode(char ch) {
            v = 1 << (ch - 'a');
        }
        TrieNode add(char ch) {
            int k = ch - 'a';
            if (next[k] != null) {
                next[k].v |= 1 << k;
            } else {
                next[k] = new TrieNode((ch));
            }
            return next[k];
        }
        TrieNode get(char ch) {
            return next[ch - 'a'];
        }
    }
    TrieNode root = new TrieNode('a');
    /**
        * Initialize your data structure here.
        */
    public Trie() {}
    /**
        * Inserts a word into the trie.
        */
    public void insert(String word) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            p = p.add(c);
        }
        p.end = true;
    }
    /**
        * Returns if the word is in the trie.
        */
    public boolean search(String word) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            p = p.get(c);
            if (p == null) {
                return false;
            }
        }
        return p.end;
    }
    /**
        * Returns if there is any word in the trie that starts with the given prefix.
        */
    public boolean startsWith(String prefix) {
        TrieNode p = root;
        for (char c : prefix.toCharArray()) {
            p = p.get(c);
            if (p == null) {
                return false;
            }
        }
        return true;
    }
}

搜索

Go语言中字符串前缀判断

func HasPrefix(s, prefix string) bool {
    return len(s) >= len(prefix) && s[0:len(prefix)] == prefix
}

// 字典树节点
type TrieNode struct {
    children map[interface{}]*TrieNode
    isEnd    bool
}
// 构造字典树节点
func newTrieNode() *TrieNode {
    return &TrieNode{children: make(map[interface{}]*TrieNode), isEnd: false}
}
// 字典树
type Trie struct {
    root *TrieNode
}
// 构造字典树
func NewTrie() *Trie {
    return &Trie{root: newTrieNode()}
}
// 向字典树中插入一个单词
func (trie *Trie) Insert(word []interface{}) {
    node := trie.root
    for i := 0; i < len(word); i++ {
        _, ok := node.children[word[i]]
        if !ok {
            node.children[word[i]] = newTrieNode()
        }
        node = node.children[word[i]]
    }
    node.isEnd = true
}
// 搜索字典树中是否存在指定单词
func (trie *Trie) Search(word []interface{}) bool {
    node := trie.root
    for i := 0; i < len(word); i++ {
        _, ok := node.children[word[i]]
        if !ok {
            return false
        }
        node = node.children[word[i]]
    }
    return node.isEnd
}
// 判断字典树中是否有指定前缀的单词
func (trie *Trie) StartsWith(prefix []interface{}) bool {
    node := trie.root
    for i := 0; i < len(prefix); i++ {
        _, ok := node.children[prefix[i]]
        if !ok {
            return false
        }
        node = node.children[prefix[i]]
    }
    return true
}