108 ms c++ binary search solution


  • 0
    X

    sort the vector based on bit-map result, then use binary search to find a range of candidates. Refer to
    http://codingmelon.com/2015/12/15/maximum-product-of-word-lengths-leetcode-318/

    class Solution {
    public:
        int maxProduct(vector<string>& words) {
            int len = words.size();
            vector<pair<int,int>> nums(len, make_pair(0, 0));
            for (int i = 0; i < len; i++) {
                nums[i].second = words[i].length();
                for (auto c : words[i]) {
                    nums[i].first |= 1 << (c - 'a');
                }
            }
            sort(nums.begin(), nums.end(), myCompare);
            int maxProd = 0;
            for (int i = len - 1; i >= 0; i--) {
                int val = nums[i].first;
                int l = nums[i].second;
                int target = 1;
                while (target <= val) {
                    target <<= 1;
                }
                target >>= 1;
                while (target) {
                    while (target & val) {
                        target >>= 1;
                    }
                    int indexRight = bsMostRight(nums, 0, i - 1, (target << 1) - 1);
                    
                    while (target && (!(target & val))) {
                        target >>= 1;
                    }
                    int indexLeft = bsMostLeft(nums, 0, i - 1, (target << 1));
                    for (int j = indexLeft; j <= indexRight; j++) {
                        if (!(nums[j].first & val)) {
                            maxProd = max(maxProd, nums[j].second * l);
                        }
                    }
                }
            }
            return maxProd;
        }
        static bool myCompare(const pair<int, int>& a, const pair<int, int>& b) {
            return a.first < b.first;
        }
        int bsMostLeft(vector<pair<int,int>>& nums, int left, int right, int val) {
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid].first < val) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            return left;
        }
        int bsMostRight(vector<pair<int,int>>& nums, int left, int right, int val) {
            while (left < right) {
                int mid = left + (right - left + 1) / 2;
                if (nums[mid].first > val) {
                    right = mid - 1;
                } else {
                    left = mid;
                }
            }
            return left;
        }
    };

  • 0
    F

    Could you please explain the code?


  • 0
    G

    The algorithm is O(n^2), where n = words.size().

    It represents a word by a bit vector, e.g., "ae" ---> 1001.

    Binary search for the range of words with 'a' or 'e', so the right would be "e..." and the left "a...".
    Then finds maxProduct of the words in above range and "ae", e.g., if "bc" in the word, then we have 2*2 = 4.

    Finding the range may save some search, e.g., for word "abcde", we do not need to search because it contains everything between 'a' and 'e'. But this does not change the complexity.

    Please correct me if I am wrong.


Log in to reply
 

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