also O(N^2), but why it is TLE?


  • 0
    J

    my code is as follows:

    int maxProduct(vector<string>& words) {
        int ret = 0;
        for (int i = 0; i < words.size(); i++) {
            for (int j = i + 1; j < words.size(); j++) {
                unordered_set<char> si(words[i].begin(), words[i].end()),
                                    sj(words[j].begin(), words[j].end());
                bool share = false;
                for (auto it = si.begin(); it != si.end(); it++) {
                    if (sj.find(*it) != sj.end()) {
                        share = true;
                        break;
                    }
                }
                if (!share) {
                    ret = max(ret, int(words[i].length()) * int(words[j].length()));
                }
            }
        }
        return ret;
    }
    

    In theory, it is O(N^2) for time complexity and O(26) that is O(1) for space complexity.

    But it is TLE.....
    who can tell me why? Is there anything wrong?


  • 1
    G

    U R not O(n^2) but O(n^2 * m), m is the length of words.


Log in to reply
 

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