# Trie SPOJ Problem - PhoneList TLE

In this problem you are given input of phone numbers and you are supposed to determine whether any number is the prefix of another. I have an addchild method that returns true or false if a given string can be inserted and is not a prefix of another string. How could I improve the efficiency of my code so that I could pass the time constraints?

http://www.spoj.com/problems/PHONELST/

import java.util.Arrays;
import java.util.Scanner;

class PhoneList {

static class Node{
Node [] children;

int value;

public Node(){
children=new Node[11];
}

public Node(int value){
children=new Node[11];
this.value=value;
}

}

static class  Trie{
Node root=null;

public Trie(){
root=new Node();
}

Node currentNode=root;
int number=0;

for(int i=0;i<s.length();i++){
number=s.charAt(i)-'0';
if(currentNode.children[currentNode.children.length-1]!=null){
return false;
}
if(currentNode.children[number]==null){
currentNode.children[number]=new Node(number);
}
currentNode=currentNode.children[number];
}

if(currentNode.children[currentNode.children.length-1]==null){
currentNode.children[currentNode.children.length-1]=new Node(10);
}else{
return false;
}

return true;
}

}

public static void main(String[] args) {
Scanner input=new Scanner(System.in);

int number_of_test_cases=input.nextInt();

boolean istrue;
for(int i=0;i<number_of_test_cases;i++){

Trie tree=new Trie();
int length=input.nextInt();
String numbers[]=new String[length];

for(int j=0;j<numbers.length;j++){
numbers[j]=input.next();
}

Arrays.sort(numbers);
istrue=true;

for(int k=0;k<numbers.length;k++){
System.out.println("NO");
istrue=false;
break;
}
}

if(istrue){
System.out.println("YES");
}
}

}

}


• Instead of children = new Node[11], I would use a Map<Integer, Node>. I'm not sure how you came up with 11.

• Sorting is quite expensive. Maybe you can solve it with a trie alone without sorting, or with sorting alone without a trie.

• Small detail: you have random gaps of 2, 3 or 4 empty lines all over the place.

EDIT:
So, instead of arguing, here is my implementation, without sorting and without a terminal value:

    public static class Node<T> {
private T value;
private Map<T, Node<T>> children = new HashMap<>();

public Node(T value) {
this.value = value;
}

public Node<T> getChild(T t) {
return children.get(t);
}

public boolean hasChildren() {
return !children.isEmpty();
}

public void addChild(T t, Node<T> child) {
children.put(t, child);
}
}

public static boolean hasConflictingPrefixes(String[] numbers) {
Node<Byte> trie = new Node<>(null);
for (String number : numbers) {
Node<Byte> currentNode = trie;
for (Byte byt : number.getBytes(Charset.forName("UTF-8"))) {
Node<Byte> childNode = currentNode.getChild(byt);
if (childNode == null) {
childNode = new Node(byt);
} else {
// current number is longer (or equal) to existing word
if (!childNode.hasChildren())
return true;
}
currentNode = childNode;
}
// current number is a prefix to another one
if (currentNode.hasChildren())
return true;
}
return false;
}


I'm not necessarily proud of this code, but it solves this problem.

Note that duplicate numbers are considered as conflicting prefixes, ie. {"911", "911"} has a conflict just as {"911", "9112"}.

• I came up with 11 because 0-9 are going to be mapped to a node that is used in a phone number and the node with index 10 signifies that a specific phone number ended. Jun 29, 2014 at 18:19
• In the construction of a trie a terminal node is needed because you can have more than one string that starts with the same prefix Jun 29, 2014 at 18:37
• In a trie if you don't have a terminal node then you wouldn't be able to tell how many strings there are that start with the same prefix... Jun 29, 2014 at 18:41
• ex: 9114 and 911 - in your case if there is no terminal node the trie would only contain 9114 acting as if there is only one string in the trie Jun 29, 2014 at 18:41
• @The Bear Wrong. And wrong to the one who upvoted your comments. See my solution. Jun 29, 2014 at 19:22