AcWing 835. Trie字符串统计 - Java实现
原题链接
简单
作者:
陆星
,
2024-04-05 22:51:10
,
所有人可见
,
阅读 3
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main solution = new Main();
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
while (n-- > 0) {
String op = scanner.next();
String word = scanner.next();
if ("I".equals(op)) {
solution.insert(word);
} else if ("Q".equals(op)) {
System.out.println(solution.query(word));
}
}
}
private void insert(String word) {
Trie node = this.root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.frequency++;
}
private int query(String word) {
Trie node = this.root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
return 0;
} else {
node = node.children[index];
if (i == word.length() - 1) {
return node.frequency;
}
}
}
return 0;
}
private final Trie root = new Trie();
private static class Trie {
private final Trie[] children;
private int frequency;
public Trie() {
this.children = new Trie[26];
this.frequency = 0;
}
}
}