Mam takie zadanie ze SPOJ-a: http://www.spoj.pl/problems/PHONELST/
I próbowałem je zrobić na kilka różnych sposobów. Niestety ciągle dostaję błąd wykonania i nie mam pojęcia dlaczego.
Oto mój kod z użyciem drzewa Trie:
import java.io.DataInputStream;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
class Glowna {
static class Parser
{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Parser(InputStream in)
{
din = new DataInputStream(in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public int nextInt() throws Exception
{
int ret = 0;
byte c = read();
while (c <= ' ') c = read();
boolean neg = c == '-';
if (neg) c = read();
do
{
ret = ret * 10 + c - '0';
c = read();
} while (c > ' ');
if (neg) return -ret;
return ret;
}
public String nextString() throws Exception
{
String ret = "";
byte c=read();
ArrayList<Byte> bytes=new ArrayList<Byte>();
while(c <= ' ') c=read();
do {
bytes.add(c);
c=read();
}
while(c>' ');
byte[] d=new byte[bytes.size()];
for(int a=0; a<bytes.size(); a++) d[a]=bytes.get(a);
ret=new String(d);
return ret.trim();
}
public String nextLine() throws Exception {
byte c=read();
while(c==10 || c==13) c=read();
ArrayList<Byte> bytes=new ArrayList<Byte>();
do {
bytes.add(c);
c=read();
}
while(c != 13 && c != 10 && c!=-1);
byte[] d=new byte[bytes.size()];
for(int a=0; a<bytes.size(); a++) d[a]=bytes.get(a);
String ret=new String(d);
return ret.trim();
}
public String readAll() throws Exception {
byte c=read();
while(c==10 || c==13) c=read();
ArrayList<Byte> bytes=new ArrayList<Byte>();
do {
bytes.add(c);
c=read();
}
while(c!=-1);
byte[] d=new byte[bytes.size()];
for(int a=0; a<bytes.size(); a++) d[a]=bytes.get(a);
String ret=new String(d);
return ret.trim();
}
private void fillBuffer() throws Exception
{
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1) buffer[0] = -1;
}
private byte read() throws Exception
{
if (bufferPointer == bytesRead) fillBuffer();
return buffer[bufferPointer++];
}
}
public static class Node {
char content;
boolean marker;
Collection<Node> child;
public Node(char c){
child = new LinkedList<Node>();
marker = false;
content = c;
}
public String toString() {
String ret=String.valueOf(content);
for(Node n: child) ret+=n.toString();
return ret;
}
public Node subNode(char c){
if(child!=null){
for(Node eachChild:child){
if(eachChild.content == c){
return eachChild;
}
}
}
return null;
}
}
public static class Trie{
private Node root;
public Trie(){
root = new Node(' ');
}
public void insert(String s){
Node current = root;
if(s.length()==0) //For an empty character
current.marker=true;
for(int i=0;i<s.length();i++){
Node child = current.subNode(s.charAt(i));
if(child!=null){
current = child;
}
else{
current.child.add(new Node(s.charAt(i)));
current = current.subNode(s.charAt(i));
}
// Set marker to indicate end of the word
if(i==s.length()-1)
current.marker = true;
}
}
public boolean search(String s){
Node current = root;
while(current != null){
for(int i=0;i<s.length();i++){
if(current.subNode(s.charAt(i)) == null)
return false;
else
current = current.subNode(s.charAt(i));
}
/*
* This means that a string exists, but make sure its
* a word by checking its 'marker' flag
*/
if (current.marker == true)
return true;
else
return false;
}
return false;
}
public boolean contains(String s){
Node current = root;
while(current != null){
for(int i=0;i<s.length();i++){
if(current.subNode(s.charAt(i)) == null) return false;
else
current = current.subNode(s.charAt(i));
}
/*
* This means that a string exists, but make sure its
* a word by checking its 'marker' flag
*/
if(current!=null) return true;
else return false;
}
return false;
}
public boolean isUnique() {
for(Node n: root.child) {
if(!isUnique(n)) return false;
}
return true;
}
public boolean isUnique(Node n) {
if(n.marker && n.child.size()>0) return false;
else for(Node k: n.child) return isUnique(k);
return true;
}
public String toString() {
String ret="";
for(Node n: root.child) if(n.marker) ret+=n.toString();
return ret;
}
}
public static void main(String[] args) throws Exception {
Parser br = new Parser(System.in);
int x=br.nextInt();
for(int i=0; i<x; i++) {
Trie drzewo=new Trie();
int numerow=br.nextInt();
boolean consistent=true;
for(int t=0; t<numerow && consistent; t++) {
String slowo=br.nextString();
drzewo.insert(slowo);
}
consistent=drzewo.isUnique();
if(consistent) System.out.println("YES");
else System.out.println("NO");
}
}
}
Będę wdzięczny za każdą pomoc