赞
踩
题目:
题解:
- class Trie {
- private Trie[] children;
- private boolean isEnd;
-
- public Trie() {
- children = new Trie[26];
- isEnd = false;
- }
-
- public void insert(String word) {
- Trie node = this;
- 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.isEnd = true;
- }
-
- public boolean search(String word) {
- Trie node = searchPrefix(word);
- return node != null && node.isEnd;
- }
-
- public boolean startsWith(String prefix) {
- return searchPrefix(prefix) != null;
- }
-
- private Trie searchPrefix(String prefix) {
- Trie node = this;
- for (int i = 0; i < prefix.length(); i++) {
- char ch = prefix.charAt(i);
- int index = ch - 'a';
- if (node.children[index] == null) {
- return null;
- }
- node = node.children[index];
- }
- return node;
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。