My C++ solutions using map and hash O(n) complexity


  • 0
    L

    This problem is quite easy to solve. The key is the matching strings that are anagrams into one bucket. So I use a key-value map to do this.
    Plus I designed a hash function myself, but it is absolutely fine using the one provided by the library.

    size_t hashValue(string str) {
        sort(str.begin(), str.end());
        int power = 1;
        size_t result = 0;
        for (char c : str) {
            result += (c - 'a' + 1)  * power;
            power *= 26;
        }
        return result;
    }
    
    vector<string> anagrams(vector<string> &strs) {
        vector<string> result;
        unordered_map<size_t, vector<string>> mp;
        
        for (string &str : strs) {
            size_t value = hashValue(str);
            mp[value].push_back(str);
        }
        
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            if (it->second.size() >= 2) {
                for (string s : it->second)
                    result.push_back(s);
            }
        }
        return result;
    }

  • 0
    L

    What if "size_t result" may not be big enough to store a long string? It seems a string with over 9 letters should overflow the size_t's range.


Log in to reply
 

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