Блог пользователя LouisCK

Автор LouisCK, 9 лет назад, По-английски

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);
                 }
            
            
            
            }
            
          
            
        }
    
    
    }
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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