目前有一堆单词，给定开头的前缀，如ab找出这对单词中以ab开头的单词。 public static

Question

目前有一堆单词，给定开头的前缀，如ab找出这对单词中以ab开头的单词。 public static void initTrie(Set sensitiveWords) { words = new HashMap(sensitiveWords.size()); Map temp; Map temp2; //遍历传入的敏感词集合，构建字典树 for (String word : sensitiveWords) { temp = words; //将每个词转为字符数组，每个字符都是一个状态，构建有限状态集合 for (char character : word.toCharArray()) { //先查看字典树内是否存在这个状态 Object var1 = temp.get(character); if (var1 != null) { //如果存在，则指向下一个节点 temp = (Map) var1; } else { //如果不存在则进行创建节点 temp2 = new HashMap(); temp2.put("isEnd", "0"); //放置该字符，并标记其状态 temp.put(character, temp2); //指向下一个节点 temp = temp2; } if (word.charAt(word.length() - 1) == character) { temp.put("isEnd", "1"); } } } System.out.println(words); } public static boolean contains(String text, int matchType) { int i = 0; while (i == text.length() - 1) { text.substring(i); } return false; } public static void main(String[] args) { initTrie(new HashSet<>(Arrays.asList("搓搓手", "扣扣脚", "深深懒腰"))); System.out.println(contains("搓手",1)); }

Answer 1

Trie树的建立—查找字典中以特定字符串开头的单词数量(java实现)

Trie树的定义
在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie这个术语来自于retrieval。根据词源学，trie的发明者Edward Fredkin把它读作/ˈtriː/ “tree”。但是，其他作者把它读作/ˈtraɪ/ “try”。

i)根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
ii)从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
iii)每个节点的所有子节点包含的字符互不相同。

优缺点
优点：插入和查询的效率很高，都为O(m)，其中 m 是待插入/查询的字符串的长度。
缺点：空间复杂度高。

应用举例
词频统计：
输入
输入的第一行为一个正整数n，表示词典的大小，其后n行，每一行一个单词（不保证是英文单词，也有可能是火星文单词哦），单词由不超过10个的小写英文字母组成，可能存在相同的单词，此时应将其视作不同的单词。接下来的一行为一个正整数m，其后m行，每一行一个字符串，该字符串由不超过10个的小写英文字母组成。
输出
对于每一个询问，输出一个整数Ans,表示词典中以给出的字符串为前缀的单词的个数。

public class p1014 {

  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int m = Integer.parseInt(sc.nextLine());
    List<String> question = new ArrayList<String>();
    for(int i=0;i < m;i++){
      question.add(sc.nextLine());
    }
    int n = Integer.parseInt(sc.nextLine());
    List<String> answer = new ArrayList<String>();
    for(int j = 0; j < n; j++){
      answer.add(sc.nextLine());
    }

    List<Integer> res = new ArrayList<Integer>();
    TrieTree tree = new TrieTree();

    for(int j=0;j<question.size();j++){
      tree.insert(question.get(j));
    }

    for(int i=0;i<answer.size();i++){
      String ans = answer.get(i);
      int r = tree.findStartWith(ans);
      res.add(r);
    }
    for(int i=0;i<res.size();i++){
      System.out.println(res.get(i));
    }
  }
}

class TrieTree{
  private class TrieNode{
    TrieNode[] children = new TrieNode[26];
    boolean isLeaf;
    char val;
    int prefixNum;
    public TrieNode(char val){
      this.val = val;
      this.isLeaf = false;
      this.prefixNum = 0;
    }
  }

  TrieNode root;
  public TrieTree(){
    root = new TrieNode(' ');
  }

  public void insert(String word){
    TrieNode cur = root;
    char[] data = word.toLowerCase().toCharArray();
    for(int i=0;i<data.length;i++){
      int index = data[i] - 'a';
      if(cur.children[index]==null){
        cur.children[index] = new TrieNode(data[i]);
      }
      cur = cur.children[index];
      cur.prefixNum++;
    }
    cur.isLeaf = true;
  }

  public int findStartWith(String s){
    TrieNode cur = root;
    char[] data = s.toLowerCase().toCharArray();
    for(int i = 0;i<data.length;i++){
      int index = data[i] - 'a';
      if(cur.children[index]==null){
        return 0;
      }
      cur = cur.children[index];
    }
    return cur.prefixNum;
  }

}