WAP to Check if if two strings are anagrams or not. in O(n) ..?

There are 4 ways to solve this problem: as i can solve it each has complexity Issue

Solution #1: Sort the strings

boolean anagram(String s, String t)
{
return sort(s) == sort(t);
}

# include
# include
# include


/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING
PURPOSE */
void exchange(char *a, char *b)
{
char temp;
temp = *a;
*a = *b;
*b = temp;
}

int partition(char A[], int si, int ei)
{
char x = A[ei];
int i = (si - 1);
int j;

for (j = si; j <= ei - 1; j++)
{
if(A[j] <= x)
{
i++;
exchange(&A[i], &A[j]);
}
}
exchange (&A[i + 1], &A[ei]);
return (i + 1);
}


/* Implementation of Quick Sort
A[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/

void quickSort(char A[], int si, int ei)
{
int pi; /* Partitioning index */
if(si < ei)
{
pi = partition(A, si, ei);
quickSort(A, si, pi - 1);
quickSort(A, pi + 1, ei);
}
}

int anagram(char* a,int a_len,char* b,int b_len)
{
quickSort(a,0,a_len);
quickSort(b,0,b_len);

return (strcmp(a,b));

}


/* Driver program to test removeDups */
int main()
{
char a[] = "madonna louise ciccone";
char b[] ="occasional nude income";
int n=sizeof(a)/sizeof(char);
int m=sizeof(b)/sizeof(char);


printf( " %d ", anagram(a,n,b,m));
getchar();
return 0;
}



TC O(nlogn)
SC O(1)
Run here https://ideone.com/swXVj

solution #2:

Check if the two strings have identical counts for each unique char.

class Anagram
{
public static void main(String a[])
{
System.out.println(anagram(new String("william shakespeare"), new String("iam aweakishspeller")));
}
public static boolean anagram(String s, String t)
{
if (s.length() != t.length()) return false;
int[] letters = new int[256];
int num_unique_chars = 0;
int num_completed_t = 0;
char[] s_array = s.toCharArray();
for (char c : s_array) { // count number of each char in s.
if (letters[c] == 0) ++num_unique_chars;
++letters[c];
}
for (int i = 0; i < t.length(); ++i) {
int c = (int) t.charAt(i);
if (letters[c] == 0) { // Found more of char c in t than in s.
return false;
}
--letters[c];
if (letters[c] == 0) {
++num_completed_t;
if (num_completed_t == num_unique_chars) {
// it’s a match if t has been processed completely
return i == t.length() - 1;
}
}
}
return false;
}
}

TC o(n)
Scv o(n)
Run here https://ideone.com/mpWTO

3rd & 4th Solution

Take XOR of both the strings ..if they are anagram then result will be zero.

Its has two way to solve & cool ,Most Efficient as I can Say to solve the problem

#include
#include
using namespace std;

int isAnagram(char* a, char* b, int len)
{
int zor = 0;
for(int i = 0; i < len; ++i)
{
zor ^= a[i] - '0';

//printf( "%d %d \t ", (a[i]-'0'),zor);

zor ^= b[i] - '0';

//printf( "%d %d \n ", (b[i]-'0'),zor);

}

if(zor == 0)
return 1;

return 0;
}

4th Solution

Check for both xor & sum of each string if xor=0 & both sum are equals then string are Anagram of each other

int check_anagram(const char* str1, const char* str2)
{
int len = strlen(str1);
int l2=strlen(str2);
if(len != l2)
return 0;

int xorval=0;
int sum1=0,sum2=0;
for(int i=0;i {
sum1 += str1[i];
sum2 += str2[i];
xorval ^= str1[i] ^ str2[i];
}

if((xorval == 0 && (sum1 == sum2))==true)
return 1;
else return 0;

return 0;
}



int main()
{
char a[] = "madonna louise ciccone";
//"william shakespeare";//"abcd";

char b[] ="occasional nude income";
//"iam aweakishspeller";//"badc";

int n=sizeof(a)/sizeof(char);//if both anagram size should be same so no issue here

printf( " %d %d ",isAnagram(a, b, n),check_anagram(a,b));

return 0;
}

TC O(n)
Sc (1)
Run Here https://ideone.com/UDk5G