C++ Trie 69ms beats 85%


  • 15
    class Solution {
    public:
        class TreeNode {
        public:
            TreeNode* next[2];
            TreeNode () {next[0] = NULL; next[1] = NULL;};
        };
        TreeNode* buildTree(vector<int>& nums) {
            TreeNode* root = new TreeNode(), *cur;
            int n = nums.size();
            for (int i = 0; i < n; i++) {
                int num = nums[i];
                cur = root;
                for (int j = 31; j >= 0; j--) {
                    int index = ((num >> j) & 1);
                    if (cur->next[index] ==  NULL)
                        cur->next[index] = new TreeNode();
                    cur = cur->next[index];
                }
            }
            return root;
        }
        
        int helper(TreeNode* cur, int num) {
            int res = 0;
            for (int i = 31; i >= 0; i--) {
                int index = ((num >> i) & 1) ? 0 : 1;
                if (cur->next[index]) {
                    res <<= 1;
                    res |= 1;
                    cur = cur->next[index];
                } else {
                    res <<= 1;
                    res |= 0;
                    cur = cur->next[index ? 0 : 1];
                }
            }
            return res;
        }
        
        int findMaximumXOR(vector<int>& nums) {
            int res = 0;
            TreeNode* root = buildTree(nums);
            
            for (auto i : nums) {
                res = max(res, helper(root, i));
            }
            
            return res;
        }
    };
    

  • 0
    P

    @yong.cao.7731 A few lines shorter for the method "helper":

        int helper(TreeNode* cur, int num) {
            int res = 0;
            for (int i = 31; i >= 0; i--) {
                int index = (num >> i) & 1;
                if (cur->next[index ^ 1]) {
                    res += 1 << i;
                    cur = cur->next[index ^ 1];
                } else {
                    cur = cur->next[index];
                }
            }
            return res;
        }

  • 1

    Thank you for sharing the brilliant answer! But I think the maximum height of the tree is only 31 instead of 32, as nums[i]< 2^31.
    So the code

    for (int j = 31; j >= 0; j--) {
        //...
    }
    

    actually could be

    for (int j = 30; j >= 0; j--) {
        //...
    }
    

  • 0
    Z
    This post is deleted!

  • 0

    @yaopiupiupiu Yes, you are correct. Thanks


  • 0
    S

    can somebody help understand how trie is helping in this problem?


  • 0
    X

    @sha256pki just traverse every input num and try to find a number x from trie tree, which can help to max num^x


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.