Group Anagrams
10.2 Group Anagrams: Write a method to sort an array of strings so that all the anagrams are next to each other.
- O(NlogN) time?, O(N) extra space
- One way of doing this is first sort the strings, and pair them into a map.
- Then we can sort the map by its second value, then return its first value.
typedef std::pair<std::string, string> p;
struct Comp {
bool operator()(const p &left, const p &right) const {
return left.first < right.second;
}
};
void group_anagrams(vector<string> &strings) {
map<string, string> word_anagram;
for (int i = 0; i < strings.size(); i++) {
string cpy = strings.at(i);
sort(strings.at(i).begin(), strings.at(i).end());
word_anagram.insert( { { cpy }, { strings.at(i) } });
}
// dump into vector in order to make it sortable
vector<pair<string, string>> cpy(word_anagram.begin(), word_anagram.end());
sort(cpy.begin(), cpy.end(), Comp());
int count = 0;
for (auto &i : cpy) {
strings.at(count++) = i.first;
}
}
int main() {
vector<string> words = {"could", "cloud", "dance", "caned", "own", "now", "clams", "calms", "wings", "swing", "a" };
group_anagrams(words);
print(words);
}
Last modified 3yr ago