41 lines
1.5 KiB
Markdown
41 lines
1.5 KiB
Markdown
# 10.2. Anagrams
|
|
|
|
> Sort an array of strings so that all the anagrams are next to each other.
|
|
|
|
Anagram: word formed by rearranging the letters of another, such as spar formed by rasp.
|
|
|
|
Each word in the array should be sorted alphabetically, and then each word sorted in the array. Can start from the beginning, sort each word, and iteratively add the new sorted word to the sorted array.
|
|
|
|
```c++
|
|
const int MAX_CHAR = 26;
|
|
|
|
// function to print string in sorted order
|
|
void sortString(string &str) {
|
|
// Hash array to keep count of characters.
|
|
// Initially count of all charters is
|
|
// initialized to zero.
|
|
int charCount[MAX_CHAR] = {0};
|
|
|
|
// Traverse string and increment
|
|
// count of characters
|
|
for (int i=0; i<str.length(); i++)
|
|
|
|
// 'a'-'a' will be 0, 'b'-'a' will be 1,
|
|
// so for location of character in count
|
|
// array we wil do str[i]-'a'.
|
|
charCount[str[i]-'a']++;
|
|
|
|
// Traverse the hash array and print
|
|
// characters
|
|
for (int i=0; i<MAX_CHAR; i++)
|
|
for (int j=0; j<charCount[i]; j++)
|
|
cout << (char)('a'+i);
|
|
}
|
|
```
|
|
|
|
which takes O(n) time and O(1) space for each word. Then, we need to group the strings in the array by anagram.
|
|
|
|
## Solution
|
|
|
|
Use a hash table mapping the sorted version of a word to a list of anagrams. `acre` maps to `{acre, race, care}`. Once we have grouped all the words into these lists by anagram, we can then put them back into the array. This is an adaptation of **bucket sort**.
|