LouisCK's blog

By LouisCK, 5 years ago, In English,

I am trying to solve this problem on SPOJ using a Trie. However, my code does not pass the time limit. This seems to be a reasonable approach for the given limits as other people seem to have used the same approach and passed the tests. I think that my Trie implementation in Java might be too slow. Could someone help me out by checking it and suggesting improvements or providing their own implementation? (in Java)

Here is my approach: There are two classes, one is Node and the other is Trie.

The Node class has two elements, Node[] arr and a boolean isLeaf.

In this problem, we need to check if any number is a prefix of another so while inserting numbers, I simply check if I am passing any node that is a leaf or if after inserting a word, the chain ends and there is no further branching from this Node.

Here is my code:

private static class Node
    {
        public boolean isLeaf;
        public Node[] arr;
        public Node()
        {
            isLeaf = false;
            arr = new Node[10];
        }
     
    }
    
    private static class Trie
    {
        public Node head;
        
        public Trie(String number)
        {
            head = new Node();
            insert(head, number, 0);
        }
       
        public boolean insert(String number)
        {
            return insert(head, number, 0);
        
        }
        
        private boolean insert(Node curr_node, String number, int curr)
        {
            int displacement = (int) number.charAt(curr) - 48;
         
            if(curr == number.length() - 1)
            {
                if(curr_node.arr[displacement] == null)
                {
                    curr_node.arr[displacement] = new Node();
                    curr_node.arr[displacement].isLeaf = true;
                    return true;
                
                }
                
                else return false;
            }
            
            else
            {
                if(curr_node.arr[displacement] == null)
                {
                    curr_node.arr[displacement] = new Node();
                    return insert(curr_node.arr[displacement], number, curr + 1);
                
                }
                
                else
                {
                    if(curr_node.arr[displacement].isLeaf) return false;
                    else return insert(curr_node.arr[displacement], number, curr + 1);
                 }
            
            
            
            }
            
          
            
        }
    
    
    }
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

No Trie required, this stupid code gets AC in 1.51 sec: http://ideone.com/ag4icA

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah I got my solution accepted by simply sorting but for future questions that may require a Trie, I wanted to know if this implementation was a good one or if there are better ways to do this.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Implement it using a matrix, check this comment: http://codeforces.com/blog/entry/13622#comment-185607