...

/

Solution: Group Anagrams

Solution: Group Anagrams

Here's a detailed analysis on how to solve the Group Anagrams problem

Solution #1: Brute Force

Press + to interact
#include <iostream>
#include <vector>
using namespace std;
void printStrArr(string arr[], int arrSize) {
for (int i = 0; i < arrSize; i++)
cout << arr[i] << endl;
}
vector <string> groupAnagrams(string arr[], int arrSize) {
string strArr[arrSize];
vector <string> output;
int count = 0, k = 0;
for (int i = 0; i < arrSize; i++) {
for (int j = 0; j < arrSize; j++) {
if(i == j)
break;
if(arr[i].length() == arr[j].length()) {
// If a character of str1 not in c2
for(int c1 = 0; c1 < arr[i].length(); c1++ ) {
for(int c2 = 0; c2 < arr[j].length(); c2++) {
if(arr[i][c1] == arr[j][c2])
count += 1;
}
}
if(count == arr[j].length()) {
output.push_back(arr[j]);
output.push_back(arr[i]);
}
count = 0;
}
}
}
return output;
}
int main() {
string arr[] = {
"tom marvolo riddle ",
"abc",
"def",
"cab",
"fed",
"clint eastwood ",
"i am lord voldemort",
"elvis",
"old west action",
"lives"
};
int arrSize = 10;
vector<string> vec;
vec = groupAnagrams(arr, arrSize);
for (std::vector<string>::const_iterator i = vec.begin(); i != vec.end(); ++i)
std::cout << *i << ' ';
}

In this solution, we check if every character of each string matches every character of some other string. If it does, we consider the pair an anagram.

Time Complexity

This solution is in O(n2k2)O(n^2k^2) ...

Access this course and 1400+ top-rated courses and projects.