CareerCup

1) a) Sort the 2 arrays b)compare each array index one by one.
2) a)add characters of str1 into a hashmap b)store the size of hashmap. c) store characters from str2 into the same hashmap. if size increases its not anagram

i) Add the letters of str1 to a hash table. Key being alphabet and value being the frequency.
ii)Keep track of length of the string, say temp.
iii) For each letter in str2, lookup the hash table:
a) Decrement the value if key is found. Decrement the temp by 1.
If temp is zero finally, anagram found.
If key is found, but value was zero then its not an anagram.

O(n) for n lookups.

add ascii values and compare

What about adding the squares of the ascii values or each character ?

I think that will be O(n) with O(1) space.

build two bitvectors bv1 and bv2
init bv1 and bv2 all zeros
for str1, for each character c, bv1 |= 1<<(c-'A')
for str2, for each character c, bv2 |= 1<<(c-'A')

then compare bv1 and bv2. O(n)
better than the sorting solution, which is O(nlogn)

<pre lang="java" line="1" title="CodeMonkey40738" class="run-this">class Anagram {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String s1 = "msassaa";
String s2 = "saamsas";
System.out.println("Is Anagram:" + isAnagram(s1, s2));

}

private static boolean isAnagram(String s1, String s2) {
if (s1.length() != s2.length())
return false;
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
int[] aMap = new int[26];
int complete = 0;
for (int i = 0; i < s1.length(); i++) {
aMap[s1.charAt(i) - 'a']++;
complete++;
}
for (int i = 0; i < s2.length(); i++) {
if (aMap[s2.charAt(i) - 'a'] > 0) {
aMap[s2.charAt(i) - 'a']--;
complete--;
if (aMap[s2.charAt(i) - 'a'] == 0) {
if (complete == 0)
return true;
}
} else {
return false;
}
}
return false;
}

}
</pre><pre title="CodeMonkey40738" input="yes">1
2
10
42
11

</pre>

AFTER REMOVIN DE BLANK SPACES,CHECK DE LENGTH OF THE 2 STRINGS,,,
IF TEY R EQUAL ,DEN SORT THE TWO ARRAYS
COMPARE BOTH THE STRINGS FOR EQUALITY.......=> anagram

thank u for ur comment gr08itz

since it's two strings, create an array of size 26. 26=Number of alphabets. Now, parse 1st string array['a']+=1 array['b']+=1...etc..
Consider second string and instead of adding subtract 1 ...I.E. array['a']-=1 etc. Iterate through the array and all elements zero it is an anagram else not.

Hash each string using some mechanism
Assuming we are dealing only with alphabets and strings are not too long
as hash might exceed data type limits.
i have assigned 2 pow for each alphabet.

so i calc hash of both string with O(n) and compare the hashes.

public static boolean IsAnagram(String s1, String s2) {
		char[] c1 = s1.toCharArray();
		char[] c2 = s2.toCharArray();
		
		if(c1.length != c2.length)
		{
			System.out.println("Length mismatch .. Not Anagrams");
			return false;
		}
		else
		{
			int s1_hash = 0,
				s2_hash = 0;
			for (int i=0; i< c1.length ; i++ )
			{
				s1_hash += hash(c1[i]);
				s2_hash += hash(c2[i]);				
			}
						
			if (s1_hash == s2_hash )
			{
				System.out.println("!! Anagrams.... !!");
				return true;
			}
			else
			{				
				System.out.println("Hash mismatch .. Not Anagrams");				
				return false;
			}
		}
			
		
	}
	
	
	static int hash(char c)
	{
		switch (c)
		{
		case 'a' : 
			return 1;
		case 'b' : 
			return 2;
		case 'c' : 
			return 4;
		case 'd' : 
			return 8;
		case 'e' : 
			return 16;
		case 'f' : 
			return 32;
		case 'g' : 
			return 64;
		case 'h' : 
			return 128;
		case 'i' : 
			return 256;
		case 'j' : 
			return 512;
		case 'k' : 
			return 1024;
		case 'l' : 
			return 2048;
		case 'm' : 
			return 4096;
		case 'n' : 
			return 8192;
		case 'o' : 
			return 16384;
		case 'p' : 
			return 32768;
		case 'q' : 
			return 65536;
		case 'r' : 
			return 131072;
		case 's' : 
			return 262144;
		case 't' : 
			return 524288;
		case 'u' : 
			return 1048576;
		case 'v' : 
			return 2097152;
		case 'w' : 
			return 4194304;
		case 'x' : 
			return 8388608;
		case 'y' : 
			return 16777216;
		case 'z' : 
			return 33554432;
		default:
			return 0;			
		}
	}