2
\$\begingroup\$

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();
    }

    boolean addChild(String s){

        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++){
        if(!tree.addChild(numbers[k])){
            System.out.println("NO");
            istrue=false;
            break;
        }
        }

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

}

}
\$\endgroup\$
1
\$\begingroup\$
  • 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);
                    currentNode.addChild(byt, childNode);
                } 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"}.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – The Bear Jun 29 '14 at 18:19
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – The Bear Jun 29 '14 at 18:37
  • 1
    \$\begingroup\$ 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... \$\endgroup\$ – The Bear Jun 29 '14 at 18:41
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – The Bear Jun 29 '14 at 18:41
  • 1
    \$\begingroup\$ @The Bear Wrong. And wrong to the one who upvoted your comments. See my solution. \$\endgroup\$ – toto2 Jun 29 '14 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.