算法基础：前缀树（Trie tree、字典树）

前缀树（Trie tree、字典树）

概念

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

前缀树的3个基本性质：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

为什么说前缀树比hash 要快：

其实hash表的查询已经做到了O（1），前缀树本身其实就是一个多层的hash树，自己的查询也是O（1），理论上不应该有更快。

但是hash表在hash字符串的时候，是整体hash的，也就是说，如果查找操作是查找整体字符串的时候，hash表就是完美的，但是如果查找操作是查找某一个前缀是否存在，那就需要前缀树了。

思路

TreeNodeStruct {
    int pass;
	int end;
	std::map<char,TreeNodeStruct*> next_node_list;
}

插入操作

拿到一组字符串之后，把每一个字符串的每一个字符拿出，进行插入，如果节点的map中发现存在该字符，就在这map中找到节点并pass+1，如果是字符串的结尾，就end+1.

如果没有在map中找到这个字符，就在map中插入这个字符，new 出对应的节点，并update pass、end 属性。

删除操作

同理如果要删除一个字符串的话，就从头遍历一次字典树，然后将沿途的pass -1，并在末尾处 end -1。

如果一个节点pass == 0， end==0，就将这个节点free 掉，并从上级的map 中删掉这个字符。

查找操作

复制一份字典树，如果想找出所有的以“xxxx”为前缀的字符串，首先先判断树中“xxxx”是否存在，如果存在就沿着树按照深度优先的方式，沿途将pass -1，直到找到end，输出该字符串，然后将end -1。 删除途中所有的空节点，然后再次执行上述操作，直到将xxxx 前缀之后的树枝前部删除。

代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <memory>

template<typename V>
class TrieMap {

public:

    class Option {
    public:
        V val{};
        bool isNone = true;
    };

private:
    class TrieNode {
    public:
        Option option;
        std::unordered_map<char, std::shared_ptr<TrieNode>> children;
    };

public:
    /***** 增/改 *****/

    // 在 Map 中添加 key
    void put(const std::string &key, V val) {
        if (!containsKey(key)) {
            word_size++;
        }

        root = putImpl(root, key, val, 0);
    }

    /***** 删 *****/

    // 删除键 key 以及对应的值
    void remove(const std::string &key) {
        if (!containsKey(key)) {
            return;
        }

        root = removeImpl(root, key, 0);

        word_size--;
    }

    /***** 查 *****/

    // 搜索 key 对应的值，不存在则返回 null
    // get("the") -> 4
    // get("tha") -> null
    TrieMap::Option get(const std::string &key) {
        auto x = getNode(root, key);
        if (x == nullptr || x->option.isNone) {
            TrieMap::Option tmp;

            return tmp;
        }

        return x->option;
    }

    // 判断 key 是否存在在 Map 中
    // containsKey("tea") -> false
    // containsKey("team") -> true
    bool containsKey(const std::string &key) {
        return !get(key).isNone;
    }

    // 在 Map 的所有键中搜索 query 的最短前缀
    // shortestPrefixOf("themxyz") -> "the"
    std::string shortestPrefixOf(const std::string &query) {
        auto p = root;
        int i = 0;
        for (auto ch: query) {
            if (!p->children.count(ch)) {
                return "";
            }

            if (!p->option.isNone) {
                return query.substr(0, i);
            }

            p = p->children[ch];
            i++;
        }

        if (p != nullptr && !p->option.isNone) {
            return query;
        }

        return "";

    }

    // 在 Map 的所有键中搜索 query 的最长前缀
    // longestPrefixOf("themxyz") -> "them"
    std::string longestPrefixOf(const std::string &query) {
        int max_len = 0;
        auto p = root;
        int i = 0;
        for (auto ch: query) {
            if (!p->children.count(ch)) {
                return "";
            }

            if (!p->option.isNone) {
                max_len = i;
            }

            p = p->children[ch];
            i++;
        }

        if (p != nullptr && !p->option.isNone) {
            return query;
        }

        return query.substr(0, max_len);
    }

    // 搜索所有前缀为 prefix 的键
    // keysWithPrefix("th") -> ["that", "the", "them"]
    std::vector<std::string> keysWithPrefix(const std::string &prefix) {
        std::vector<std::string> res{};

        auto x = getNode(root, prefix);

        if (x == nullptr) {
            return res;
        }

        traverse(x, prefix, res);
        return res;

    }

    // 判断是和否存在前缀为 prefix 的键
    // hasKeyWithPrefix("tha") -> true
    // hasKeyWithPrefix("apple") -> false
    bool hasKeyWithPrefix(const std::string &prefix) {
        return getNode(root, prefix) != nullptr;
    }

    // 通配符 . 匹配任意字符，搜索所有匹配的键
    // keysWithPattern("t.a.") -> ["team", "that"]
    std::vector<std::string> keysWithPattern(const std::string &pattern) {
        std::vector<std::string> res{};
        traversePattern(root, "", pattern, 0, res);
        return res;
    }

    // 通配符 . 匹配任意字符，判断是否存在匹配的键
    // hasKeyWithPattern(".ip") -> true
    // hasKeyWithPattern(".i") -> false
    bool hasKeyWithPattern(const std::string &pattern) {
        return hasKeyWithPatternImpl(root, pattern, 0);
    }

    // 返回 Map 中键值对的数量
    int size() {
        return word_size;
    }


private:
    std::shared_ptr<TrieNode> getNode(std::shared_ptr<TrieNode> node, const std::string &key) {
        auto p = node;

        if (node == nullptr) {
            return nullptr;
        }

        for (auto ch: key) {
            if (!p->children.count(ch)) {
                return nullptr;
            }

            p = p->children[ch];
        }

        return p;
    }


    void traverse(std::shared_ptr<TrieNode> node, std::string path, std::vector<std::string> &res) {
        if (node == nullptr) {
            return;
        }

        if (!node->option.isNone) {
            res.push_back(path);
        }

        for (const auto &item: node->children) {
            path.push_back(item.first);
            traverse(item.second, path, res);
            path.erase(path.end());
        }
    }

    void traversePattern(std::shared_ptr<TrieNode> node, std::string path, const std::string &pattern, int i,
                         std::vector<std::string> &res) {
        if (node == nullptr) {
            return;
        }

        if (i == pattern.length()) {
            if (!node->option.isNone) {
                res.push_back(path);
            }
            return;
        }

        char c = pattern[i];

        if (c == '.') {
            for (const auto &item: node->children) {
                path.push_back(item.first);
                traversePattern(item.second, path, pattern, i + 1, res);
                path.erase(path.end());
            }
        } else {
            path.push_back(c);
            traversePattern(node->children[c], path, pattern, i + 1, res);
            path.erase(path.end());
        }
    }

    bool hasKeyWithPatternImpl(std::shared_ptr<TrieNode> node, std::string pattern, int i) {
        if (node == nullptr) {
            return false;
        }

        if (i == pattern.length()) {
            return !node->option.isNone;
        }

        char c = pattern[i];
        if (c != '.') {
            return hasKeyWithPatternImpl(node->children[c], pattern, i + 1);
        }

        for (const auto &item: node->children) {
            if (hasKeyWithPatternImpl(item.second, pattern, i + 1)) {
                return true;
            }
        }

        return false;
    }

    std::shared_ptr<TrieNode> putImpl(std::shared_ptr<TrieNode> node, const std::string &key, V val, int i) {
        if (node == nullptr) {
            node = std::make_shared<TrieNode>();
        }

        if (i == key.length()) {
            node->option.isNone = false;
            node->option.val = val;
            return node;
        }

        char c = key[i];

        node->children[c] = putImpl(node->children[c], key, val, i + 1);
        return node;
    }


    std::shared_ptr<TrieNode> removeImpl(std::shared_ptr<TrieNode> node, const std::string &key, int i) {
        if (node == nullptr) {
            return nullptr;
        }

        if (i == key.length()) {
            node->option.isNone = true;
        } else {
            char c = key[i];
            node->children[c] = removeImpl(node->children[c], key, i++);
        }


        if (!node->option.isNone) {
            return node;
        }

        for (auto item: node->children) {
            return node;
        }

        return nullptr;
    }

private:
    int word_size = 0;
    std::shared_ptr<TrieNode> root{};
};

class TrieSet {
    // 底层用一个 TrieMap，键就是 TrieSet，值仅仅起到占位的作用
    // 值的类型可以随便设置，我参考 Java 标准库设置成 Object
private:
    TrieMap<int> map{};

    /***** 增 *****/

    // 在集合中添加元素 key
public:
    void add(const std::string &key) {
        map.put(key, -1);
    }

    /***** 删 *****/

    // 从集合中删除元素 key
    void remove(const std::string &key) {
        map.remove(key);
    }

    /***** 查 *****/

    // 判断元素 key 是否存在集合中
    bool contains(const std::string &key) {
        return map.containsKey(key);
    }

    // 在集合中寻找 query 的最短前缀
    std::string shortestPrefixOf(const std::string &query) {
        return map.shortestPrefixOf(query);
    }

    // 在集合中寻找 query 的最长前缀
    std::string longestPrefixOf(const std::string &query) {
        return map.longestPrefixOf(query);
    }

    // 在集合中搜索前缀为 prefix 的所有元素
    std::vector<std::string> keysWithPrefix(const std::string &prefix) {
        return map.keysWithPrefix(prefix);
    }

    // 判断集合中是否存在前缀为 prefix 的元素
    bool hasKeyWithPrefix(const std::string &prefix) {
        return map.hasKeyWithPrefix(prefix);
    }

    // 通配符 . 匹配任意字符，返回集合中匹配 pattern 的所有元素
    std::vector<std::string> keysWithPattern(const std::string &pattern) {
        return map.keysWithPattern(pattern);
    }

    // 通配符 . 匹配任意字符，判断集合中是否存在匹配 pattern 的元素
    bool hasKeyWithPattern(const std::string &pattern) {
        return map.hasKeyWithPattern(pattern);
    }

    // 返回集合中元素的个数
    int size() {
        return map.size();
    }
};


class Trie {
public:
    Trie() {

    }

    TrieSet mSet;


    void insert(std::string word) {
        mSet.add(word);
    }

    bool search(std::string word) {
        return mSet.contains(word);
    }

    bool startsWith(std::string prefix) {
        return mSet.hasKeyWithPrefix(prefix);
    }

};

int main() {
    printf("hello world \n");

    Trie trie;
    trie.insert("apple");
    auto res = trie.search("apple");   // 返回 True
    std::cout << res << std::endl;
    res = trie.search("app");     // 返回 False
    std::cout << res << std::endl;
    res = trie.startsWith("app"); // 返回 True
    std::cout << res << std::endl;
    trie.insert("app");
    res = trie.search("app");     // 返回 True
    std::cout << res << std::endl;
}

算法考题

leetcode 212 单词搜索（hard） trie+dfs

题目描述

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

输入:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]

输出: ["eat","oath"]
说明:
你可以假设所有输入都由小写字母 a-z 组成。

思路

1. 把words 中的字符串用字典树进行存储。
2. 二维数组是一个图，所以可以从每一个节点开始做深度优先的遍历，并跟踪遍历过程形成的字符串x，每遍历一个位置就将x 与字典树中存储的字符串进行find，如果存在就将x输出，同时将之前图中被深度遍历形成x的值设置为#（无效字符），之后的节点在遍历中一旦遇到无效字符就结束遍历。
3. 将整个图每一个节点就遍历一遍（已经被设置为无效节点的除外）

代码

class Trie{
private:
    bool is_string;
    Trie *next[26];
    string str;    
public:
    Trie(){
        is_string=false;
        str="";
        memset(next,0,sizeof(next));
    }
    void insert(string word)//插入单词，建立前缀树
    {
        Trie *root=this;
        for(auto w:word)
        {
            if(root->next[w-'a']==nullptr)root->next[w-'a']=new Trie();
            root=root->next[w-'a'];
        }
        root->is_string=true;
        root->str=word;
    }
    
    void search(vector<string>& result,vector<vector<char>>& board)
    {
        Trie *root=this;
        for(int i=0;i<board.size();++i)//每一个坐标都要开始dfs
            for(int j=0;j<board[0].size();++j)
                helper(result,board,root,i,j);
    }
    
    void helper(vector<string>& result,vector<vector<char>>& board,Trie* note,int x,int y)
    {
        if(note->is_string==true){//在board中找到words中一个单词，添加到result中
            note->is_string=false;//将该单词标记为false,防止在word中再次递归到这个单词，从而造成重复添加
            result.push_back(note->str);
            return;
        }
        if(x<0||x==board.size()||y<0||y==board[x].size())return;//超出边界,不能继续递归
        if(board[x][y]=='#'||note->next[board[x][y]-'a']==nullptr)return;//坐标(x,y)对应的字符不在前缀树中，递归方向不对，返回到上一个坐标
        note=note->next[board[x][y]-'a'];//note指向下一个字符节点
        char temp=board[x][y];
        board[x][y]='#';//标记(x,y)对应的字符已被访问过，防止同一个单元格内的字符在一个单词中重复使用
        helper(result,board,note,x+1,y);
        helper(result,board,note,x-1,y);
        helper(result,board,note,x,y+1);
        helper(result,board,note,x,y-1);
        board[x][y]=temp;
    }
};
class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Trie *root=new Trie();
        vector<string> result;
        for(auto word:words)
            root->insert(word);
        root->search(result,board);
        return result;
    }
};