CareerCup

new code

public static void printAnagram(String [] collection,String target)
	{
		for(int i=0;i<collection.length;i++)
		{
			if(isAnagram(collection[i],target))
				System.out.println(collection[i]);
		}
	}
	public static boolean isAnagram(String m,String b)
	{
		if(m.length()!=b.length())
			return false;
		int [] counts1=counts(m);
		int [] counts2=counts(b);
		for(int i=0;i<counts1.length;i++)
		{
			if(counts1[i]!=counts2[i])
				return false;
		}
		return true;
	}
	public static int[] counts(String m)
	{
		int[] count=new int[256];
		for(int i=0;i<count.length;i++)
			count[i]=0;
		for(int i=0;i<m.length();i++)
		{
			count[m.charAt(i)]++;
		}
		return count;
	}

A String of size n has n! anagrams. O(n2) algorithm is impossible. O(n!) is the best you can do.

Lets say there's m different strings, and each string is on average n letters long

Make a copy of the original array, lets call this c-arr
Sort each string in c-arr alphabetically (ie. the words car, rac, and arc all become acr). should be m*n log n
Sort the string you want to find anagrams of alphabetically (big O of nlogn)
run through c-arr, and compare your sorted string with the elements in c-arr (big O of m * n at worst, you can easily make it better)
If you hit a match, then for that index in c-arr, print or do whatever operation you have to on the original array at the same position

total big O: m*n log n + nlogn + m * n = nlogn +m*n, which is n^2 or less

public class Anagrams {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] stringSet = new String[]{"car","arc","art","arct","rac"};
String target = "car";
int n= stringSet.length;
for(int i=0; i<n; i++) {
if(target.length()==stringSet[i].length()){
if(isAnagrams(target,stringSet[i])){
System.out.println(stringSet[i]);
}
}
}


}

public static String sort(String s){
char[] arr = s.toCharArray();
java.util.Arrays.sort(arr);
return new String(arr);
}

public static boolean isAnagrams(String target, String current){
if(sort(target).equals(sort(current)))
return true;
return false;
}

}

can you please explain runtime complexity of this algorithm ? why are you creating hashtable everytime for target ?

There are N strings in an array, and you need to find all the anagram of a given string in this array. Suppose all the strings are composed of 26 lowercase characters, then use 26 different prime numbers to represent the 26 characters(eg. 2, 3, 5, 7...), then for every string in this array, compute the product of all the character in this string, and compare with the product of the given string, if equal, it is the anagram of the given string. O(n^2) time complexity.
eg. abc = 2*3*5 = cab = 5*2*3

Working code: ideone.com/eiFQn

void sort(char str[5][10],int i)
{
int p=0,q=0;
char temp;
int length=strlen(str[i]);

for(p=0;p<length;p++)
{
for(q=p;q<length;q++)
{
if(str[i][p]> str[i][q])
{
temp=str[i][p];
str[i][p]=str[i][q];
str[i][q]=temp;
}
}
}


}


int main()
{
char str[5][10]={"CAR","ARC","ATUL","RADHA","RAC"};
int i=0,count=0;
char test[]="ACR";

while(i<5)
{
sort(str,i);
i++;
}

i=0;
while(i<5)
{
if(!strcmp(str[i],test))
count++;
i++;
}


}

HashMap<String, TreeSet<String>

public class Anagrams {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] stringSet = new String[]{"car","arc","art","arct","rac"};
String target = "car";
int n= stringSet.length;
for(int i=0; i<n; i++) {
if(target.length()==stringSet[i].length()){
if(isAnagrams(target,stringSet[i])){
System.out.println(stringSet[i]);
}
}
}


}

public static String sort(String s){
char[] arr = s.toCharArray();
java.util.Arrays.sort(arr);
return new String(arr);
}

public static boolean isAnagrams(String target, String current){
if(sort(target).equals(sort(current)))
return true;
return false;
}

}

public static void printAnagrams(String[] strArr, String target){
if(strArr == null){
System.out.println("Error");
}
for(int i = 0; i < strArr.length; i++){
if(isAnagram(strArr[i], target){
System.out.println( strArr[i] + "is Anagram of" + target)
}
}
}

private static boolean isAnagram(Sting str1, String tar){
if(str1.length() != tar.length() || str.equals(tar)){
return false;
}
int[] freq = new int[256];

for(int i = 0; i < str1.length(); i++){
int charInt = str.charAt(i);
freq[charInt]++;
}

for(int j = 0; j < tar.length(); j++){
int charInt2 = tar.charAt(j);
if(--freq[charInt2] < 0){
return false;
}
}
return true;
}

O(N^2) time O(N^2) space

public void findAnagram(String[] strings, String s) {
        HashMap<String, List<String>> map = new HashMap<String, List<String>> ();
        for (String element: strings) {
                  List<String> value;
              if (map.containsKey(sort(element))) {value = map.get(sort(element)); }
                else {value = new LinkedList<String>();}
                value.add(element); 
                map.put(sort(element), value);
        }
        printAnagrams(s, map);
}
public String sort(String s) {
       char[] array = s.toCharArray();
       Arrays.sort(array);
       return new String(array);
}

public void printAnagrams(String s, HashMap<String, List<String>> map) {
     if(map.containsKey(sort(s)) {
        for (String anagram: map.get(sort(s)).toArray(new String[0])) {
              System.out.println("anagram of s: "+ anagram);
        }
     }

It fails for input String[] stringSet = new String[]{"car","arc","artc","arct","rac","cccc"};
String target = "arct";

#include <stdio.h>
#include <string.h>
int check_anagram(char [], char []);

int main(void)
{
char *a="suresh", *b="reshsu";

if (check_anagram(a, b)== 1)
printf("\"%s\" and \"%s\" are not anagrams.\n", a, b);
else
printf("\"%s\" and \"%s\" are anagrams.\n", a, b);

return 0;
}

int check_anagram(char a[], char b[])
{
int hash[26] = {0},c = 0;

while (a[c] != '\0')
{
hash[a[c]-'a']++;
hash[b[c]-'a']--;
c++;
}

for(c=0;c<26;c++){
if(hash[c] != 0)
return 1;
}
return 0;
}

public static ArrayList<String> get_anagrams_results(String[] test,String aim){
ArrayList<String> results=new ArrayList<String>();
for(int i=0;i!=test.length;i++){
if(isAnagrams(test[i],aim)){
results.add(test[i]);
}
}
return results;
}
public static boolean isAnagrams(String o1,String o2){
if(o1.length()!=o1.length()){
return false;
}

int[] holdChar=new int[256];
for(int i=0;i!=o1.length();i++){
holdChar[(int)o1.charAt(i)]++;
}
for(int i=0;i!=o2.length();i++ ){
if(--holdChar[(int)o2.charAt(i)]==-1){
return false;
}
}
return true;
}

public static void findAnagrams(String[] m,String target)
	{
		for(int i=0;i<m.length;i++)
		{
			if(isAnagrams(m[i],target))
				System.out.println(m[i]);
		}
	}
	public static boolean isAnagrams(String a,String b)
	{
		if(a.length()!=b.length())
		{
			return false;
		}
		else
		{
			Hashtable<Character,Integer> ht1=createHashTable(a);
			Hashtable<Character,Integer> ht2=createHashTable(b);
			Set<Character> characters=ht1.keySet();
			Iterator<Character> iterator=characters.iterator();
			while(iterator.hasNext())
			{
				Character single=iterator.next();
				if(!(ht2.containsKey(single.charValue())&&ht2.get(single.charValue())==ht1.get(single.charValue())))
					return false;
			}
		}
		return true;
		
	}
	public static Hashtable<Character,Integer> createHashTable(String a)
	{
		Hashtable<Character,Integer> hashTable=new Hashtable<Character,Integer>();
		for(int i=0;i<a.length();i++)
		{
			if(hashTable.contains(a.charAt(i)))
			{
				int value=hashTable.get(a.charAt(i));
				value++;
				hashTable.remove(a.charAt(i));
				hashTable.put(a.charAt(i),value);
			}
			else
				hashTable.put(a.charAt(i),1);
		}
		return hashTable;
	}