Buzz words

给你一个字符串和字典,从头扫到位,如果到当前的字符的字符串存在于字典中,则显示 buzz.

例子:

ILOVEPINEAPPLEJUICE

字典:

[pine, apple, pineapple, juice, applejuice]

那么当我们到达ILOVEPINE的时候,就要buzz,当我们到达APPLE的时候,也要buzz,当我们到达JUICE的时候,也要buzz.

 public class Solution {

     public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("apple");
trie.insert("pie");
trie.insert("applejuice");
trie.insert("juice"); Solution s = new Solution();
s.buzz("applepiejuice", trie.root);
} public void buzz(String str, Node root) {
List<Node> list = new ArrayList<Node>();
List<Node> temp = new ArrayList<Node>();
list.add(root);
for (int i = ; i < str.length(); i++) {
for (Node node : list) {
Node child = node.getChildNode(str.charAt(i));
if (child != null) {
temp.add(child);
if (child.isEnd) {
System.out.println("buzz");
}
}
}
if (i != ) {
Node child = root.getChildNode(str.charAt(i));
if (child != null) {
temp.add(child);
if (child.isEnd) {
System.out.println("buzz");
}
}
} list = temp;
temp = new ArrayList<Node>();
} }
} class Trie {
Node root; public Trie() {
root = new Node(' ');
} public void insert(String word) {
if (exists(word))
return;
Node current = root;
for (int i = ; i < word.length(); i++) {
char ch = word.charAt(i);
Node node = current.getChildNode(ch);
if (node == null) {
current.map.put(ch, new Node(ch));
current = current.getChildNode(ch);
} else {
current = node;
}
}
current.isEnd = true;
} public boolean exists(String word) {
Node current = root;
for (int i = ; i < word.length(); i++) {
char ch = word.charAt(i);
current = current.getChildNode(ch);
if (current == null) {
return false;
}
}
if (current.isEnd) {
return true;
} else {
return false;
}
} } class Node {
char ch;
boolean isEnd;
Map<Character, Node> map; public Node(char ch) {
this.ch = ch;
map = new HashMap<Character, Node>();
} public Node getChildNode(char ch) {
return map.get(ch);
}
}
上一篇:基于Ubuntu Hadoop的群集搭建Hive


下一篇:轻量级OLAP(二):Hive + Elasticsearch