频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
字典树模板(java)
2015-06-06 08:43:38         来源:my_acm  
收藏   我要投稿
class Trie{
	private int SIZE=26;
	private TrieNode root;//字典树的根

	Trie(){//初始化字典树
		root=new TrieNode();
	}

	private class TrieNode{//字典树节点
		private int num;//有多少单词通过这个节点,即节点字符出现的次数
		private TrieNode[]  son;//所有的儿子节点
		private boolean isEnd;//是不是最后一个节点
		private char val;//节点的值

		TrieNode(){
			num=1;
			son=new TrieNode[SIZE];
			isEnd=false;
		}
	}

	//建立字典树
	public void insert(String str){//在字典树中插入一个单词
		if(str==null||str.length()==0){
			return ;
		}
		TrieNode node=root;
		char[] letters=str.toCharArray();
		for(int i=0,len=str.length();i < len;i++){
			int pos=letters[i]-'a';
			if(node.son[pos]==null){
				node.son[pos]=new TrieNode();
				node.son[pos].val=letters[i];
			}else{
				node.son[pos].num++;
			}
			node=node.son[pos];
		}
		node.isEnd=true;
	}

	//计算单词前缀的数量
	public int countPrefix(String prefix){
		if(prefix==null || prefix.length()==0){
			return -1;
		}
		TrieNode node=root;
		char[] letters=prefix.toCharArray();
		for(int i=0,len=prefix.length();i具体看百科:https://baike.baidu.com/link?url=bImDvvYau9FWbZKr64ExkxvXOZb_Df-b7O2YCPHyqH_orknkoOi6JT4O-3a9XqorwbugAnTibEq0pFjx-Gvu8_
点击复制链接 与好友分享!回本站首页
相关TAG标签 字典 模板
上一篇:图片实现默认下载而不是打开图片(Java版)
下一篇:jstack命令使用
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站