Trie C++ AC


  • 0
    class TrieNode{
    public:
    //bool isEnd = false;
    TrieNode(){}
    vector<TrieNode*> vec = {nullptr, nullptr};
    };
    class Solution {
    public:
    int find(TrieNode* root, int num){
        int ans = 0, j = 31;
        while(j != -1 && root){
            int first = 1 & (num>>j);
            if(root->vec[!first] != nullptr){
                ans = (ans<<1) | 1;
                root = root->vec[!first];
            }else{
                ans = ans<<1;
                root = root->vec[first];
            }
            j--;
        }
        return ans;
    }
    int findMaximumXOR(vector<int>& nums) {
        if(nums.size() < 2) return 0;
        TrieNode* root = new TrieNode();
        //construct Trie
        for(auto num : nums){
            TrieNode* root2 = root;
            int j = 31;
            while(j != -1){
                int first = 1 & (num>>j);
                if(root2->vec[first] == nullptr){
                    root2->vec[first] = new TrieNode();
                }
                root2 = root2->vec[first];
                j--;
            }
            //root2->isEnd = true;
        }
        
        int res = 0;
        for(auto num : nums){
            auto root2 = root;
            res = max(res, find(root2, num));
        }
        return res;
    }
    };

Log in to reply
 

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