快把单词的存储都改成字典树吧

快把单词的存储都改成字典树吧"/>

快把单词的存储都改成字典树吧

概述

​ 在计算机科学中，trie，又称前缀树或字典树。与二叉查找树不同，值不是直接保存在结点中，而是结点在树中的位置决定。一个结点的所有子孙都有相同的前缀，也就是这个结点对应的字符串，而根节点对应空字符串。

​ Trie的典型应用是用于统计，它的优点是：利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较。

时间复杂度

在这里插入图片描述

结点结构

每个结点都有若干向下个结点的指针

    //创建结点private class Node {boolean isWord;String val;Map<Character, Node> next;public Node() {this("");}public Node(String val) {this.val = val;this.isWord = false;this.next = new HashMap<>();}}

    private int size;private Node root;public Trie() {this.size = 0;this.root = new Node();}public int getSize() {return this.size;}

添加元素

将单词拆解成每个字符，然后添加到字典树中，到最后一个字符时判断那个位置是否是单词（判断isWord），如果不是，则改成是单词

    public void addStr(String str) {if (str.isEmpty() || str == null) {return;}Node cur = root;for (int i = 0; i < str.length(); i++) {char c = str.charAt(i);Map<Character, Node> children = cur.next;if (!children.containsKey(c)) {children.put(c, new Node(cur.val + c));}cur = children.get(c);}if (!cur.isWord) {cur.isWord = true;this.size++;}}

查询操作

查找是否存在指定单词

一直跟着单词往下寻找就行

    // 判断是否存在指定的单词public boolean matchWord(String word) {if (word.isEmpty() || word == null) {return false;}Node cur = root;for (int i = 0; i < word.length(); i++) {char c = word.charAt(i);Map<Character, Node> children = cur.next;if (!children.containsKey(c)) {return false;}cur = children.get(c);}return cur.isWord;}

查找是否存在以指定前缀开始的单词

先找前缀是否存在，然后再向下判断每一个分支是否有单词

方法一

    // 判断是否存在以pre开始的单词public boolean matchStartPre(String pre) {if (pre.isEmpty() || pre == null) {return false;}Node cur = root;for (int i = 0; i < pre.length(); i++) {char c = pre.charAt(i);Map<Character, Node> children = cur.next;if (!children.containsKey(c)) {return false;}cur = children.get(c);}return true;}

方法二

    //查找是否存在匹配前缀的单词public boolean search(String express) {if (express == null || express.length() == 0) {return false;}return match(root, express, 0);}private boolean match(Node node, String express, int index) {if (index == express.length()) {return node.isWord;}char c = express.charAt(index);Map<Character, Node> children = node.next;if (c != '.') {if (!children.containsKey(c)) {return false;}return match(children.get(c), express, index + 1);} else {for (Map.Entry entry : children.entrySet()) {if (match((Node) entry.getValue(), express, index + 1)) {return true;}}return false;}}

查找皮匹配前缀的所有单词

先找出前缀，然后从前缀的最后一个单词开始，从它的孩子中寻找单词，使用递归方式将所有分支都进行查找

    //查找匹配的单词public List<String> matchStartPreWords(String express) {List<String> list = new ArrayList<>();if (express.length() != 0 || express != null) {match(root, express, 0, list);}return list;}//递归把前缀去掉，前缀之后开始进双重递归找单词private void match(Node node, String express, int index, List<String> list) {if (index == express.length()) {findWords(node, list);return;}char c = express.charAt(index);Map<Character, Node> map = node.next;if (c != '.') {if (!map.containsKey(c)) {return;} else {match(map.get(c), express, index + 1, list);}} else {for (Map.Entry entry : map.entrySet()) {match((Node) entry.getValue(), express, index + 1, list);}}}//双重递归找到单词private void findWords(Node node, List<String> list) {if (node.isWord) {list.add(node.val);}if (node.next.size() == 0) {return;}Map<Character, Node> children = node.next;for (Map.Entry entry : children.entrySet()) {findWords((Node) entry.getValue(), list);}}

删除操作

1、如果单词是另外一个单词的前缀，只需要将单词的最后一个结点的isWord修改成false。

2、如果单词的所有字符都没有分支，删除整个单词

3、如果单词除了最后一个字符，其他的字符存在多个分支

4、对第二种情况的补充：如果单词的所有字符都没有分支，但是存在前缀作为单词的情况，例如：pan,panda,在删除panda时，使用第三种情况进行处理（node.next.size() == 1 && node.isword)

    // 删除单词public void deleteWord(String word) {if (word.length() == 0 || word == null) {return;}Node cur = root;Node mulitNode = null;int mulitIndex = -1;for (int i = 0; i < word.length(); i++) {char c = word.charAt(i);Map<Character,Node> children = cur.next;if (!children.containsKey(c)){return;}else {Node node = children.get(c);if (node.next.size()>1 || (node.isWord && node.next.size()==1)){mulitNode = node;mulitIndex = i;}cur = node;}}//真正的删除操作if (cur.isWord){if (cur.next.size()>0){cur.isWord = false;}else if (mulitNode == null){root.next.remove(word.charAt(0));}else {mulitNode.next.remove(word.charAt(mulitIndex+1));}this.size--;}}