leetcode Quesion 6: Anagram

Anagram

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Analysis:

Anagrams is two strings are using the same characters. 

One way to compare two strings is use sort(). e.g. 

sort(str1.begin(), str1.end()); 

sort(str1.begin(), str1.end());

if (str1.compare(str2)==0) // when two strings are equal, the func returns 0

A more efficient way:

1. Scan the whole string vector, for each string, store to a hash map with the "ordered string" as the key. O(n).

2. Scan the whole hash map, output the values where for one key the number of value >=2. O(n)

Note:

1. We can use multimap<string, string> in c++, which allows the duplicate key values.

2. To store key-value into multimap, use ".insert(pair<key_type, value_type>(key,value))"

3. Use "pair<multimap<string,string>::iterator,multimap<string,string>::iterator> ret;" and
    ".equal_range()" which returns a iterator pair(ret) that the "first" is the lower bound and "second" is the upper bound, to get all the key-values pairs for one key.
4. To check the number of values in one key, use the .count(key) method.

Updated 201312
Use one map <sorted string as the key,  position of the first string(unsorted)>, can deal with this problem more space efficiently.
Check the array once, if the current string is not found in the map, then add <sorted string, current position>  into the map. If the current string can be found in the map, then add the current string in the result array, at this time, the first string of this anagram added in the map should also be put into the result array only once! Change the  map value can determine that.

Code(updated 201312):

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        vector<string> res;
        map<string,int> mp;
        for (int i=0;i<strs.size();i++){
            string ss = strs[i];
            sort(ss.begin(),ss.end());
            if (mp.find(ss)!=mp.end()){
                res.push_back(strs[i]);
                if (mp[ss]!=-1){
                    res.push_back(strs[mp[ss]]);    
                    mp[ss]=-1;
                }
            }else{
                mp[ss]=i;
            }
        }
        return res;
    }
};

Updated 201309

Just use the map data structure to store, and use sort algorithm to check the anagram.

Code (updated 201309):

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        map<string,int> mp; //store the occurrence of strings, keys are sorted string
        map<string,string> pre; //store the first-time string
        vector<string> res;  //result vector
        for (int i=0;i<strs.size();i++){
            string s = strs[i]; //current string
            sort(s.begin(),s.end()); // get the key (sorted string)
            if (mp.find(s)==mp.end()){ // if this is the 1st time meet this string
                mp[s]=1; // set occurence to 1
                pre[s] = strs[i]; // save the original string
            }else{ // if anagrams found
                mp[s]++;
                if (mp[s]==2){res.push_back(pre[s]);} // need to push the 1st string into result only once
                res.push_back(strs[i]); // push the current string
            }
        }
        return res;
    }
};

Old versions:

The source code O(n^2):

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<string>res;
        if (!strs.empty()){
            vector<string>::iterator it1,it2;
            map<string int="int"> hmap;
            for (it1 = strs.begin();it1!=strs.end();it1++){
                for (it2 = it1+1;it2!=strs.end();it2++){
                    string s1 = *it1;
                    string s2 = *it2;
                    if(*it1==*it2){
                        hmap[*it1]=2;
                    }else{
                        sort(s1.begin(),s1.end());
                        sort(s2.begin(),s2.end());
                        if(s1.compare(s2)==0){
                            hmap[*it1]=1;
                            hmap[*it2]=1;
                        }
                    }
                }
            }
            map<string, int>::iterator it3;
            for (it3 = hmap.begin(); it3!=hmap.end();it3++){
                if ((*it3).second==1){
                    res.push_back((*it3).first);
                }
                if ((*it3).second==2){
                    res.push_back((*it3).first);
                    res.push_back((*it3).first);
                }
            }
        }
        return res;
    }

The source code: O(n)

class Solution {
public:
 vector<string> anagrams(vector<string> &strs) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<string> res; //result vector
        set<string> order;   //string keys (ordered charactors)
        if (!strs.empty()){
            multimap<string,string> mmp; //hash map storing all the strings
            multimap<string,string>::iterator iit;
            vector<string>::iterator it; //scan the string vector
            for (it = strs.begin(); it!= strs.end();it++){
                string ss =  *it;
                sort(ss.begin(),ss.end()); //sort the string (if isanagram, the sorted string would be the same)
                mmp.insert(pair<string,string>(ss,*it)); //store in the hash map
                order.insert(ss); //store the key.
            }
             
            pair<multimap<string,string>::iterator,multimap<string,string>::iterator> ret;
            set<string>::iterator oit;
            for (oit=order.begin(); oit!=order.end(); oit++){ // for each key loop
                if (mmp.count(*oit) > 1){                     // anagram only if the number >1
                    ret = mmp.equal_range((*oit));  //get all the pairs with the specific key
                    for (iit=ret.first; iit!=ret.second; ++iit){ 
                        res.push_back((*iit).second);
                    }
                }
                 
            }
        }
        return res;
    }
};