My O(M*N) time complexity and Space O(26 *n) accepted solution 49 ms


  • 0
    D
    vector<string> anagrams(vector<string> &strs) {
        string tplate;
        for (char c = 'a'; c <= 'z'; c++) tplate.push_back(1);
        
        vector<string> results;
        
        unordered_map<string, int> M;  // hash value to first insertion string index. or -1 if it already found an anagram
        for (int i = 0; i < strs.size(); i++)
        {
            string hashValue = tplate;
            string& sTmp = strs[i];
            for (int j = 0; j < sTmp.size(); j++)
            {
                int pos = sTmp[j] - 'a';
                hashValue[pos] += 1;
            }
            
            if (M.end() == M.find(hashValue))
                M[hashValue] = i;
            else
            {
                int index = M[hashValue];
                if (index >= 0)
                {
                    results.push_back(strs[index]);
                    M[hashValue] = -1;
                }
    
                results.push_back(sTmp);
            }
        }
        
        return results;
    }

  • 0
    D

    Nice thought! I've been trying to figure out a way to solve it using bit, but I can't..


Log in to reply
 

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