CareerCup

approach 1: naive: check every character of string 1 with every other character of string 2, O(n2)

approach 2: sort both strings and check similarity, O(nlog n)

approach 3: take a hash table and hash all characters of string1 and check whether all characters of string 2 matches O(n) time O(n) space

approach 4: take a 256 size character array where all elements are initially 0 and then every ith element takes count of that character occurance in string 1. Then for every occurance of that character in string 2, decrease that count by 1. Finally check whether all elements has count==0

O(n) tima, O(1) space

int main(){
int j=0,i=0;
int angm_flag;
int org_len,angm_len;
printf("Enter the original String\n");
gets(org_str);
printf("Enter the anagram String\n");
gets(angm_str);

org_len = strlen(org_str);
angm_len = strlen(angm_str);

if(org_len !=angm_len )
{
printf("The Strings may not be anagrams since the lengths itself different from each other\n");
return;
}

for(i=0;i<org_len;i++)
{
angm_flag =1;
for(j=0;j<angm_len;j++)
{
if(org_str[i]==angm_str[j])
{
printf("%c\t%c\n",org_str[i],angm_str[j]);
angm_flag = 0;
angm_str[j] = '*';
break;
}
}
if(angm_flag != 0)
{
printf("The above two strings are not anagrams\n");
return;
}
}
printf("Anagram String\n");
}

public class Anagram{

public static void main(String[] args){

String[] a = {"car","arc"};
String target = "car";

for(int i=0;i<a.length;i++){
if(target.length() == a[i].length()){
if(isAnagram(a[i], target))
System.out.println(a[i]);
}
}
}
public static boolean isAnagram(String a, String target){
if(sort(a).equals(sort(target)))
return true;

return false;
}
public static String sort(String arr){
char[] ch = arr.toCharArray();
Arrays.sort(ch);
return new String(ch);
}
}

If 2 strings are anagram, they contain same number of same characters, as in "tom marvolo riddle" and "i am lord voldemort".

Lowercase hack won't really work due to the localization.

public boolean isAnagram(String s1, String s2)
    {
        if (s1 == null || s2 == null)
        {
            return false;
        }
        int length = s1.length();
        if (length != s2.length())
        {
            return false;
        }
        HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();
        HashMap<Character, Integer> map2 = new HashMap<Character, Integer>();

        for (int i = 0; i<length; i++)
        {
            Character c = s1.charAt(i);
            if (map1.containsKey(c))
            {
                Integer x = map1.get(c);
                map1.put(c, x + 1);
            }
            else
            {
                map1.put(c, 1);
            }
            c = s2.charAt(i);
            if (map2.containsKey(c))
            {
                Integer x = map1.get(c);
                map2.put(c, x + 1);
            }
            else
            {
                map2.put(c, 1);
            }
        }
        if (map1.size() != map2.size())
        {
            return false;
        }
        Iterator it = map1.entrySet().iterator();
        while (it.hasNext())
        {
            Map.Entry pairs = (Map.Entry)it.next();
            Character key = (Character)pairs.getKey();
            if (!map2.containsKey(key) || !map2.get(key).equals(pairs.getValue()))
            {
                return false;
            }
        }
        return true;
    }

Exor the two strings char by char..... if they are anagrams they will cancel each other out...