How to sort an array of strings with anagrams next to each other

Question

How to sort an array of strings with anagrams next to each other?

Eg:

input {god, dog, abc, cab, man}
output {abc, cab, dog, god, man}

My approach: Sort the array ( without considering the anagrams case) in O(nlogn). Next, pick up the first string & create a histogram for the string, and compare the histogram with the remaining strings histograms in the array and place the matching strings at appropriate position of the array ..repeat until it reaches array size.. this algo takes worst case of O(n^3) (if we assume that in worst case, each string is also of size n) & extra space for the histogram representation

Histogram approach taken from the ref: finding if two words are anagrams of each other

Can we do better than this?

Answer 1

You can certainly do better as follows:

1. Loop through the array of strings
2. For each string, first sort its characters, using the sorted string as key and original string as value, put into a hash table. you will end up with a hash table that with keys as sorted strings, and values being all anagrams, meanwhile, those values are ordered. You may use map<string, set<string> > to serve for this purpose.
3. iterate over the hash-table and output all anagrams together for a given key, they should be next to each other

Assume the length of strings are M and size of array is N the time complexity is then: O(NMlogM), M is usually smaller than N in average. So this is much more efficient than what you have said.

Answer 2

#include <vector>
#include <unordered_map>
#include <string>
#include <set>
#include <algorithm>
#include <iostream>

using namespace std;

vector<string> sort_string_anagram(vector<string> array)
{
    unordered_map<string, set<string>> anagram;

    for(string word : array)
    {
      string sorted_word(word);

      sort(sorted_word.begin(),sorted_word.end());

      anagram[sorted_word].insert(word);
    }

    sort(array.begin(), array.end());

    vector<string> result;

    for(string word : array)
    {
        unordered_map<string,set<string>>::iterator iter;

        string sorted_word(word);

        sort(sorted_word.begin(), sorted_word.end());

        if( (iter = anagram.find(sorted_word)) != anagram.end() )
        {
           for(set<string>::iterator it = (iter->second).begin(); it!= (iter->second).end();++it)
           {
              result.push_back(*it);
           }
           anagram.erase(iter);
        }
    }
    return result;
}

@Jitendard, @taocp, a complete solution with time complexity: O( N(MlogM) + NlogN + N(MlogM + A) ). N is array size, M is word size, A is the maximum number of anagram that exists for a word

Answer 3

In python this can be done by:

sorted(word_list, key=lambda word: ''.join(sorted(word.replace(" ", "").lower())))

where the key is the sorted alphabetical order of character. The key will be same for anagrams, thus keeping them together

Answer 4

@Song Wang : Even I was thinking of doing it that way. But how do you know the order in which to put strings once you take them out of the hashmap ? Suppose you extract
K1 = "abc", V1 = "cab"
K2 = "abc", V2 = "abc"
How would you know which one to put first in the list 1 or 2 ?
Maybe you'll sort them again. But , then that'll be bad for the complexity.

Answer 5

Why sort in the first place? Cant you just divide the array into subsets based on anagrams. Sort the subsets and finally merge based on the first word in each subset.

Answer 6

putting this in a 'real' java programming context (i.e. we use some existing and basic jdk util classes, i think the following approach may give another interesting aspect to this topic (i.e. "how to sort an array of strings with anagrams next to each other"):

(a) we define a comparator to tell if two strings are anagrams; (b) we use Arrays.sort(array, comparator) to sort the array;

below is the code and result (the idea can be seen in chapter 9, "cracking the coding interview" by Gayle Laakmann, for example)

import java.util.Arrays;
import java.util.Comparator;

public class SolutionForSortArraysByAnagrams {

    public static void main(String[] args){

        String[] strArray = new String[]{"abets","mates","baste","meats", "betas","beast", "steam", "tames", "beats", "teams"}; 

        sortArraysByAnagrams(strArray);

        for(String str : strArray){
            System.out.println(str);
        }

    }

    private static void sortArraysByAnagrams(String[] strArray) {

        Arrays.sort(strArray, new AnagramComparator());

    }

}


class AnagramComparator implements Comparator<String> {

    @Override
    public int compare(String s1, String s2) {

        //check edge conditions and length
        if( s1 == null || s2 == null)
            return -1;
        if( s1.length() <  s2.length())
            return -1;
        else if ( s1.length() >  s2.length())
            return 1;

        //sort s1 and s2 to compare:
        //System.out.println(s1 + " vs  " + s2);        
        return sort(s1).compareTo(sort(s2));

    }

    private String sort(String s1) {
        char[] cArray = s1.toCharArray();
        Arrays.sort(cArray);        
        //System.out.println(" sorted:  " + new String(cArray));
        return new String(cArray);
    }


}

input: {"abets","mates","baste","meats", "betas","beast", "steam", "tames", "beats", "teams"};

output: abets baste betas beast beats mates meats steam tames teams

Answer 7

found the solution from the internet:

public static void sortStringWithAnagrams(String[] stringArray) {
    Arrays.sort(stringArray, new AnagramComparator());
}

public static class AnagramComparator implements Comparator<String> {

    public String getSortedString(String s) {
        char[] content = s.toCharArray();
        Arrays.sort(content);
        return new String(content);
    }

    public int compare(String s1, String s2) {
        return getSortedString(s1).compareTo(getSortedString(s2));
    }

}

Answer 8

import java.util.Arrays;
import java.util.Comparator;

/**
 * Sort an array of strings so that all anagrams are next to each other
 * @author asharda
 *
 */
public class Anagram implements Comparator<String> {


  public static String  anagram(String input)
  {
    char []s=input.toCharArray();
    Arrays.sort(s);
    return new String(s);
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub

    String arr[]= {"abc","god","cab","dog"};
    Arrays.sort(arr, new Anagram());
    for(String s:arr)
    System.out.println(s);

  }
  @Override
  public int compare(String arg0, String arg1) {
    return arg0.compareTo(arg1);
  }


}

//Credit to Cracking Coding Interview by Gayle Laakmann

Answer 9

 private static String[] getSortedAnagram(String[] array) {
    Map<String, ArrayList<String>> sortedMap = new HashMap<>();
    for (String a : array) {
        String sortedString = a.chars().sorted().
                collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString();
        sortedMap.computeIfAbsent(sortedString, s->new ArrayList<>()).add(a);
    }
   String[] output = new String[array.length];
   List<String> list = sortedMap.values().stream().flatMap(List::stream).collect(Collectors.toList());
   return list.toArray(output);
}