[Java] Solution using Prefix Tree O(len(N)) | Explained | Review please
Haven\'t seens this approach yet.\nThe idea is to use Trie, to have the branch factor 10, instead of 2 as in BST.\nEach Node contains an array of 10 elements [0
Haven\'t seens this approach yet.\nThe idea is to use Trie, to have the branch factor **10**, instead of **2** as in BST.\nEach Node contains an array of 10 elements [0-9] and marker is this node is a final digit of the number.\nSo, for input 1 000 000, there is only 6 levels in the tree.\n\nTime complexity: O(len(N)), where len(N) is number of digits in the input.\nSpace complexity: O(N)\nNumber of digits is not counted, because I assume with many inputs they will overlap all the time. \nActually, it might be even better, since Nodes are re-used by different numbers.\nNot quite sure in this estimation though.\n\nSo, while it\'s basically TreeSet, not HashSet, it should operate with constant time, not logarithmic time. \n\nWhat I know that can be optimized:\n* Do not create an array Node[10] until smth is added to the node\n* Set node a null, on remove operation, if it\'s the last node \n\nHaven\'t done this optimizations yes, because they make code messy while fighting NPE.\n\nWhat do you think? Any other possibe improvements?\n\n\n```\npublic class DesignHashSet_705 {\n\n    Node root = new Node();\n\n    public void add(int key) {\n        Node current = root;\n        do {\n            int rem = key % 10;\n            key /= 10;\n            if (current.digits[rem] == null) current.digits[rem] = new Node();\n            current = current.digits[rem];\n        } while (key > 0);\n        current.isNumber = true;\n    }\n\n    public void remove(int key) {\n        Node current = root;\n        do {\n            current = current.digits[key % 10];\n            key /= 10;\n            if (current == null) return;\n        } while (key > 0);\n        current.isNumber = false;\n    }\n\n    public boolean contains(int key) {\n        Node current = root;\n        do {\n            current = current.digits[key % 10];\n            key /= 10;\n        } while (current != null && key > 0);\n        return current != null && current.isNumber;\n    }\n\n\n    static class Node {\n        Node[] digits = new Node[10];\n        boolean isNumber = false;\n    }\n}\n\n```
['Java']