Как отсортировать массив строк с анаграммами рядом друг с другом

Question

Как отсортировать массив строк с анаграммами рядом друг с другом?

Например:

вход {бог, собака, азбука, кабина, человек}
выход {азбука, кабина, собака, бог, человек}

Мой подход: Сортировка массива (без учета случай анаграмм) в O (nlogn). Затем, возьмите первую строку &, создайте гистограмму для строки и сравните гистограмму с гистограммами оставшихся строк в массиве и поместите соответствующие строки в соответствующее положение массива. Repeat, пока не достигнет размера массива .. this алго имеет худший случай O (N^3) (если предположить, что в худшем случае, каждая строка также размера п) & дополнительное пространство для представления гистограммы

Гистограмма подход от исх: finding if two words are anagrams of each other

Можем ли мы сделать это лучше?

Answer 1

Зачем сортировать в первую очередь? Не могли бы вы просто разделить массив на подмножества на основе анаграмм. Сортируйте подмножества и, наконец, объедините их на основе первого слова в каждом подмножестве.

Answer 2

Вы, конечно, можно сделать лучше в следующем:

1. Loop через массив строк
2. Для каждой строки, первого сортировать свои символы, используя отсортированный строку как ключ и исходной строки в качестве значения, положить в хэш-таблицу. вы получите хеш-таблицу, которая с ключами в виде отсортированных строк, а значения - все анаграммы, между тем эти значения упорядочены. Вы можете использовать map<string, set<string> > для обслуживания этой цели.
3. итерация по хеш-таблице и вывода все анаграммы вместе для данного ключа, они должны быть рядом друг с другом

Предположим, длину струн М и размер массива N временная сложность тогда: O (NMlogM), M обычно меньше, чем N в среднем. Так что это намного эффективнее, чем вы сказали.

Answer 3

@Song Wang: Даже я думал об этом так. Но как вы знаете порядок, в который нужно поместить строки, как только вы вынимаете их из хэш-карты? Предположим, вы извлекаете
K1 = "ABC", V1 = "кабина"
K2 = "ABC", V2 = "ABC"
Как вы знаете, какой из них поставить первым в списке 1 или 2?
Возможно, вы будете отсортировать их снова. Но тогда это будет плохо для сложности.

Answer 4

В питоне это может быть сделано:

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

где ключ является отсортированный в алфавитном порядке характера. Ключ будет таким же для анаграмм, таким образом сохраняя их вместе

Answer 5

, помещая это в «реальный» контекст программирования java (т.мы используем некоторые существующие и базовые классы jdk util, я думаю, что следующий подход может дать еще один интересный аспект этой теме (например, «как отсортировать массив строк с анаграммами рядом друг с другом»):

(a) we определить компаратор, чтобы определить, являются ли две строки анаграммами; (b) мы используем массив Arrays.sort (массив, компаратор) для сортировки массива;

ниже код и результат (идею можно увидеть в главе 9, «взломав интервью кодирования» по Гейл Laakmann, например)

импорта java.util.Arrays; импорт java.util.Comparator;

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()); 

} 

}

класс AnagramComparator реализует компаратор {

@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); 
} 

}

вход: { "подстрекает", "товарищей", "Baště «мясо», «бета», «зверь», «пар», «приручение», «бьет», «команды»};

выход: подстрекает Колотите беты животное бьет помощников мяса пара приручает команды

Answer 6

#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, полное решение с временной сложностью: O (N (MlogM) + NlogN + N (MlogM + A)). N является размером массива, М размера слова, А максимальное число анаграммы, что существует слово

Answer 7

нашел решение из Интернета:

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)); 
    } 

}