admin 管理员组

文章数量: 887007

lintcode 442实验Trieste

描述

实现一个 Trie，包含 insert, search, 和 startsWith 这三个方法。

样例

思路

在了解字典树的性质和结构之后，就容易理解这次要求的是与之相似的三个功能：插入，查找，前缀查找。

插入操作：

建立结点pre，复制root。在pre的children[index]存放插入词汇word的第i个字符（用数字0到25表示a~z的26个字母，记作index），依次类推。若当前的children不存在，则建立大小为26的children结点数组。若children结点数组里的第index个TrieNode为空，则放入新的值为word.charAt(i)的TrieNode。然后pre前进到当前结点的children，pre.children[index]，继续循环操作word的下一个字符。直到放入word的最后一个字符以后，修改pre.exist值为true，说明pre之前的分支完整放入了word。

 

查找操作：

同插入一样，复制root到结点pre，然后遍历查找word的每一个字符word.charAt(i)，若循环里某个pre.children[index]不存在，或者word的最后一个字符的exist标记为false，则返回false。否则，循环结束，返回true。

 

前缀查找操作：唯一和查找操作不同的地方，是不要求word的最后一个字符的exist标记为true。只要遍历完String prefix，就返回true。

/*** Your Trie object will be instantiated and called as such:* Trie trie = new Trie();* trie.insert("lintcode");* trie.search("lint"); will return false* trie.startsWith("lint"); will return true*/
class TrieNode {// Initialize your data structure here.boolean exist;char ch;TrieNode[] children;public TrieNode() {}public TrieNode(char ch) {this.ch = ch;}
}public class Trie {private TrieNode root;public Trie() {root = new TrieNode();}// Inserts a word into the trie.public void insert(String word) {if (word == null || word.length() == 0) return;TrieNode pre = root;for (int i = 0; i < word.length(); i++) {if (pre.children == null) pre.children = new TrieNode[26];int index = word.charAt(i) - 'a';if (pre.children[index] == null) {pre.children[index] = new TrieNode(word.charAt(i));}pre = pre.children[index];if (i == word.length()-1) pre.exist = true;}}// Returns if the word is in the trie.public boolean search(String word) {if (word == null || word.length() == 0) return false;TrieNode pre = root;for (int i = 0; i < word.length(); i++) {int index = word.charAt(i) - 'a';if (pre.children == null || pre.children[index] == null) return false;if (i == word.length()-1 && pre.children[index].exist == false) return false;pre = pre.children[index];}return true;}// Returns if there is any word in the trie// that starts with the given prefix.public boolean startsWith(String prefix) {if (prefix == null || prefix.length() == 0) return false;TrieNode pre = root;for (int i = 0; i < prefix.length(); i++) {int index = prefix.charAt(i) - 'a';if (pre.children == null || pre.children[index] == null) return false;pre = pre.children[index];}return true;}
}

这次的题有些麻烦，还是在网上查找相关资料才能最终完成这个结果

 

转载于:.html

本文标签： lintcode 442实验Trieste

版权声明：本文标题：lintcode 442实验Trieste 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732351827h1533296.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。