C++ Trie 69ms beats 85%


  • 14
    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?


Log in to reply
 

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