Skip to content

Instantly share code, notes, and snippets.

@KodeSeeker
Created August 8, 2014 03:34
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save KodeSeeker/8c29857f423387678c09 to your computer and use it in GitHub Desktop.
Save KodeSeeker/8c29857f423387678c09 to your computer and use it in GitHub Desktop.
Group all Anagrams in Stream of Input Words
/**
* Sorting approach
* Sort each letter from the input.Keep sorted word as the key with a list of strings that are anagrams.
**/
public void groupAnagrams( String in)
{
if (str==null)
return;
HashMap<String,List<String>> map = new HashMap<String,List<String>>();
String [] str= in.split(,);
for (String s : str)
{
String tmp=s;
char[] schars= s.tocharArray();
Arrays.sort(schars);// sorted each string.
String newStr=new String(schars);
List<String> strList= new ArrayList<String>();
if(map.contains(newStr))
{
strList= map.get(newStr);
}
strList.append(tmp);
map.put(newStr,strList);
}
// so now map has the following entries
// {"aab",["aab","baa","aba"])
for(Map.Entry<String,List<String> entry: map.entrySet())
{
List <String> entryList= entry.getValue();
for(String s: entryList)
{
System.out.print(s);
}
System.out.println();
}
}
/**
* One other approach to avoid sorting would be to create a charMap. to acheive the effect of a sorted key
* */
public groupAnagrams(String str)
{
char[] strArray= str.split(",");
Map<List<Integer>, List<String>> map = new HashMap<List<Integer,List<String>>();
for (String s: strArray)
{
int[] charMap= getCharMap(s);
List<Integer> charList= Arrays.asList(charMap);
List<String> strList= new ArrayList<String>();
if(map.contains(newStr))
{
strList= map.get(charList);
}
strList.append(tmp);
map.put(charList,strList);
}
}
//abba returns [a-2,b-2]
public int[] getCharMap(String s)
{
int[] map= new int[26];
for (char c: str.tocharArray())
{
map[(int)c]++;// updates the count of the character
}
return map;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment