package com.shundong.utils; import java.util.ArrayList;
import java.util.Iterator;
import java.util.List; /**
* 一个只能处理26个字母的单词树（trie)
* 空间换时间 T(n) = O(n)
* ps:如果缺陷 欢迎留言
* @author shundong
* @data 2018-10-13
*/ public class FindWordsTrie{
//一个Trie树有一个根节点
private Vertex root; //内部类or节点类
protected class Vertex{
protected int words;
protected int prefixes;
//每个节点包含26个子节点(类型为自身)
protected Vertex[] edges;
Vertex() {
words = 0;
prefixes = 0;
edges = new Vertex[26];
for (int i = 0; i < edges.length; i++) {
edges[i] = null;
}
}
} public FindWordsTrie () {
root = new Vertex();
} /**
* 列出List所有单词
* @return
*/
public List< String> listAllWords() { List< String> words = new ArrayList< String>();
Vertex[] edges = root.edges; for (int i = 0; i < edges.length; i++) {
if (edges[i] != null) {
String word = "" + (char)('a' + i);
depthFirstSearchWords(words, edges[i], word);
}
}
return words;
} /**
* Depth First在Trie中搜索单词并将它们添加到List中。
* @param words
* @param vertex
* @param wordSegment
*/
private void depthFirstSearchWords(List words, Vertex vertex, String wordSegment) {
Vertex[] edges = vertex.edges;
boolean hasChildren = false;
for (int i = 0; i < edges.length; i++) {
if (edges[i] != null) {
hasChildren = true;
String newWord = wordSegment + (char)('a' + i);
depthFirstSearchWords(words, edges[i], newWord);
}
}
if (!hasChildren) {
words.add(wordSegment);
}
} public int countPrefixes(String prefix) {
return countPrefixes(root, prefix);
} private int countPrefixes(Vertex vertex, String prefixSegment) {
if (prefixSegment.length() == 0) { //到达单词的最后一个字符
return vertex.prefixes;
}
char c = prefixSegment.charAt(0);
int index = c - 'a';
if (vertex.edges[index] == null) { // 这个词不存在
return 0;
} else {
return countPrefixes(vertex.edges[index], prefixSegment.substring(1));
}
} public int countWords(String word) {
return countWords(root, word);
} private int countWords(Vertex vertex, String wordSegment) {
if (wordSegment.length() == 0) { //到达单词的最后一个字符
return vertex.words;
}
char c = wordSegment.charAt(0);
int index = c - 'a';
if (vertex.edges[index] == null) { // 这个词不存在
return 0;
} else {
return countWords(vertex.edges[index], wordSegment.substring(1));
} }
/**
* 在Trie上添加一个单词
* @param word 要添加的词
*/
public void addWord(String word) {
addWord(root, word);
}
/**
* 添加指定顶点的单词
* @param vertex 指定的顶点
* @param word 要添加的词
*/
private void addWord(Vertex vertex, String word) {
if (word.length() == 0) { //如果已添加该单词的所有字符
vertex.words ++;
} else {
vertex.prefixes ++;
char c = word.charAt(0);
c = Character.toLowerCase(c);
int index = c - 'a';
if (vertex.edges[index] == null) { //如果边缘不存在
vertex.edges[index] = new Vertex();
}
addWord(vertex.edges[index], word.substring(1)); //去下一个
}
}
//简单的测试测试
public static void main(String args[])
{
FindWordsTrie trie = new FindWordsTrie();
trie.addWord("cabbage");
trie.addWord("cabbage");
trie.addWord("cabbage");
trie.addWord("cabbage");
trie.addWord("cabin");
trie.addWord("berte");
trie.addWord("cabbage");
trie.addWord("english");
trie.addWord("establish");
trie.addWord("good"); // System.out.println(trie.root.prefixes);
// System.out.println(trie.root.words);
// List< String> list = trie.listAllWords();
// Iterator listiterator = list.listIterator();
// //遍历
// while(listiterator.hasNext())
// {
// String str = (String)listiterator.next();
// System.out.println(str);
// }
int count = trie.countPrefixes("c");//此处传参
int count1=trie.countWords("cabbage");
System.err.println("单词c 前缀个数为:"+count);
System.err.println("cabbage 单词的个数为:"+count1);
}
}