The complexity of my method is O(32N), but get TLE.


  • 1
    E

    When I sort every string, I get AC. I doubt whether the test cases are reasonable.

    Below is my code. For every string, I construct a fingerprint(the variable s in my code) to identify it.

    class Solution {
    public:
        vector<string> anagrams(vector<string> &strs) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            unordered_set<string> marks;
            unordered_map<string, string> d_marks;
            vector<string> ret;
            map<char, int> d;
            for (size_t i = 0; i < strs.size(); ++i) {
                d.clear();
                for (size_t j = 0; j < strs[i].size(); ++j)
                    d[strs[i][j]] = d[strs[i][j]] + 1;
                string s;
                for (char c = 'a'; c <= 'z'; ++c) {
                    stringstream ss;
                    ss << d[c];
                    s += "-" + ss.str();
                }
                if (d_marks.find(s) == d_marks.end()) {
                    d_marks[s] = strs[i];
                } else {
                    ret.push_back(strs[i]);
                    if (marks.find(s) == marks.end()) {
                        ret.push_back(d_marks[s]);
                        marks.insert(s);
                    }
                }
            }
            return ret;
        }
    };

  • 1
    S

    You construct a stringstream object too much times, which is potentially very expensive.

    Change your part of code
    from

            string s;
            for (char c = 'a'; c <= 'z'; ++c) {
                stringstream ss;
                ss << d[c];
                s += "-" + ss.str();
            }
    

    to

            string s;
            stringstream ss;
            for (char c = 'a'; c <= 'z'; ++c) {
                ss << '-' << d[c];
            }
            s = ss.str();
    

    Then it will get accepted.

    PS. Here is a comparison among several ways convert string to integer in c++, you could have a look.


  • 0
    E

    Cool. Thanks a lot.


  • 0
    Z

    I cannot see why your algorithm is O(32N). Actually you use a lot of library functions here, like d_mark.find(), or marks.insert(). You may assume that d_mark is a hashtable so the find() will probably cost O(1), but it is not guaranteed. Also, marks is a set, as far as I know, set is implemented by red-black tree, so the insert will probably cost O(lgN). So don't claim your algorithm is O(N) just because there is only one for loop.


Log in to reply
 

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