CareerCup

Sort the two strings and compare the characters. If any1 character doesnt match these are anagrams else they are not

traverse through the array and call a hashkey() funtion for each charecters which will return an unique key. The sums of these keys can be maintained for both strings , if the sums match in the end , then , they are anagrams . timecomplexity....o(n)

boolean anagram(String s, String t){
		if (s.length() != t.length())
			return false;
		int[] letters = new int[256];
		int unique_num_s = 0;
		int completed_num_s = 0;
		
		for(int i = 0; i < s.length(); ++i){
			if (letters[s.charAt(i)] == 0){
				unique_num_s++;
			}
			letters[s.charAt(i)]++;
		}
		for (int i = 0; i < t.length(); ++i){
			int c = t.charAt(i);
			if (letters[c] == 0)
				return false;
			letters[c]--;
			if (letters[c] == 0){
				completed_num_s++;
				if(unique_num_s == completed_num_s){
					return i == (t.length() - 1);
				}
			}
		}
		return false;
	}

//check if two Unicode strings are anagrams or not
class HashTable
{
public:
HashTable();
~HashTable();

int Put(WCHAR key, unsigned value);
int Get(WCHAR key, unsigned &value);
int Increment(WCHAR key, unsigned &value);
int Decrement(WCHAR key, unsigned &value);
};
int isAnagrams(LPWSTR pwszS1, LPWSTR pwszS2, BOOL &result)
{
int rv = 0;
HashTable *ht = new HashTable();
unsigned value = 0;
unsigned uniqueChars = 0;
unsigned completedChars = 0;
unsigned i = 0;
unsigned size = 0;

result = FALSE;

if (ht == NULL)
{
rv = -1;
goto exit;
}

if (pwszS1 == NULL)
{
if (pwszS2 == NULL)
{
result = TRUE;
}
goto exit;
}

size = wcslen(pwszS1);
if (size != wcslen(pwszS2))
{
goto exit;
}

for (i=0; i<size; i++)
{
if (ht->Increment(pwszS1[i], value))
{
rv = -1;
goto exit;
}
if (value == 1)
{
uniqueChars++;
}
}

for (i=0; i<size; i++)
{
if (ht->Get(pwszS2[i], value))
{
rv = -1;
goto exit;
}

if (value==0)
{
result = FALSE;
goto exit;
}
if (value==1)
{
completedChars++;
if (completedChars == uniqueChars)
{
result = i==size-1;
goto exit;
}
}

if (ht->Put(pwszS2[i], value-1))
{
rv = -1;
goto exit;
}
}

exit:
if (ht)
{
delete ht;
}
return rv;
}

strcat the first string with itself and check whether the second string is a substring of the first.

space complexity O(n)

3 loops each with order N

1. char hash[128] memset all to 0
2. if lengths are not same, just break and print not anagrams
3. go into loop whenever u encounter an element increment the particular index by 1

go through the index if anything mod 2 is not equal to 0, then they re not angrams !

simple

<pre lang="" line="1" title="CodeMonkey28380" class="run-this">
class Solution1 {
public boolean areAnagrams(String a, String b) {
int la = a.length();
int lb = b.length();
if(la == 0) return lb == 0;
else if(lb == 0) return la == 0;
else if (la != lb) return false;
for(int i = 0; i < la; ++i) {
if(a.charAt(i) != b.charAt(lb - (i + 1))) {
return false;
}
}
return true;
}

public static void main(String[] args) {
Solution1 instance = new Solution1();
System.out.println(instance.areAnagrams("", ""));
System.out.println(instance.areAnagrams("", "A"));
System.out.println(instance.areAnagrams("A", ""));
System.out.println(instance.areAnagrams("ABC", "CBA"));
System.out.println(instance.areAnagrams("ABC", "ABC"));
System.out.println(instance.areAnagrams("ABC", "BA"));
}
}
</pre><pre title="CodeMonkey28380" input="yes">
</pre>

<pre lang="" line="1" title="CodeMonkey42021" class="run-this">// Sorry about that
import java.util.HashMap;
import java.util.Map;


class Solution1 {

Map<Character, Integer> countChars(String aString) {
Map<Character, Integer> counter = new HashMap<Character, Integer>();
for(int i = 0; i < aString.length(); ++i) {
char curChar = aString.charAt(i);
Integer count = counter.get(curChar);
if(count == null) {
count = new Integer(1);
} else {
count++;
}
counter.put(curChar, count);
}
return counter;
}

public boolean areAnagrams(String a, String b) {
int la = a.length();
int lb = b.length();
if(la == 0) return lb == 0;
else if(lb == 0) return la == 0;
else if (la != lb) return false;
return countChars(a).equals(countChars(b));
}

public static void main(String[] args) {
Solution1 instance = new Solution1();
System.out.println(instance.areAnagrams("", ""));
System.out.println(instance.areAnagrams("", "A"));
System.out.println(instance.areAnagrams("A", ""));
System.out.println(instance.areAnagrams("ABC", "CBA"));
System.out.println(instance.areAnagrams("ABC", "ABC"));
System.out.println(instance.areAnagrams("ABC", "ABCC"));
System.out.println(instance.areAnagrams("ABC", "BA"));
}
}
</pre><pre title="CodeMonkey42021" input="yes">
</pre>

void anagram()
{
char s[100],t[100];
int len;
printf("Enter first string\n");
scanf("%s",s);
printf("Enter second string\n");
scanf("%s",t);
len=strlen(s);
if(len==strlen(t))
{
int res=0,i;
for(i=0;i<len;i++)
{
res=res+s[i];
res=res-t[i];
}
if(res==0)
printf("ANAGRAM\n");
else
printf("Not anagram\n");
}
else
printf("Not anagram\n");

}

So couple of strategies here
1. have an array of int from 1-256 and increment the count of each bit for the corresponding hit
2. Convert them to a upper or lowerbase generate hash for the string - ofcourse the hash algo should be strong
3. Do a sort of the string and compare.

How about using a bitset:

public static boolean areAnagram(String a, String b){

boolean areAnagram = false;

if(a.length()==b.length()){

int count = 0;

char[] aArray = a.toCharArray();
char[] bArray = b.toCharArray();

boolean[] bitSet = new boolean[256];

for(int i=0;i<aArray.length;i++){

bitSet[aArray[i]] = true;
}

for(int i=0;i<bArray.length;i++){

if(bitSet[bArray[i]]==true)
count++;
}

if(count==a.length())
areAnagram = true;
}

return areAnagram;
}

Here is my solution for this one.

public class AnagramCheck {
    //remove whitespaces, ignore case, merge sort and check?
    public static boolean checkAnagram(String input1, String input2)
    {

        if (input1.length() == input2.length())
        {
            //remove whitespaces
            input1 = input1.replaceAll("\\s", "");
            input2 = input2.replaceAll("\\s", "");
            input1 = input1.toLowerCase();
            input2 = input2.toLowerCase();
         char[] charArray1 = input1.toCharArray();
         char[] charArray2 = input2.toCharArray();
        Arrays.sort(charArray1); //dual-pivot quicksort O(n log n)
        Arrays.sort(charArray2); //dual-pivot quicksort O(n log n)
            //O(2nlogn) at this point
            boolean temp = false;
            //one pass of n needed since lengths should be equal so total O(3n log n)
            for (int i = 0; i < charArray1.length; i++)
            {
                  if (charArray1[i] == charArray2[i])
                  {
                      temp = true;
                  } else {
                      temp = false;
                  }
            }
            return temp;
        }
        return false;
    }
    public static void main(String[] args)
    {
        String input1 = "MAry";
        String input2 = "Army";
        System.out.println(checkAnagram(input1, input2));
    }
}

Approach 2> Time O(2n) Space O(1)
Maintain a 26 size array, each character represents a character
For every occurence of a character in String 1 increment the count at the index position by 1
For every occurence of a character in String 2 decrement the count at the index position by 1
After traversing through all the characters check if the sum of values at all the index positions is 0. in O(1) time

This C# simple code check for anagrams

public static void Main(string[] args)
{
string str1 = "maada";
string str2 = "aamda";
int sum1 = 0;
int sum2 = 0;

str1 = str1.Replace(" ", "");
str2 = str2.Replace(" ", "");

foreach (char alp in str1)
            {
                sum1 = sum1 + (int)alp;
            }
            foreach (char alp in str2)
            {
                sum2 = sum2 + (int)alp;
            }

            if(sum1==sum2)
            {
                Console.WriteLine("strings are anagrams");
                Console.ReadLine();
            }
        }

BOOL is Anagram(char *str1, char *str2, unsigned size)
{
for (int i = 0; i < size/2; i++)
{
if (str1[i] != str2[size-i])
return FALSE;
}
return TRUE;
}

Simple take two arrays and keep on incrementing the index values corresponding to the ASCII values of the characters in two strings, if arrays match completely the strings are anagrams.