Как бы вы отсортировали строки так, чтобы анаграммы были близки друг к другу в C++?

Question

Это было бы действительно реализовать в Java, так как вы могли бы использовать Comparator и встроенные методы для сортировки массивов символов и сравнения строк следующим образом:

public class AnagramComparator implements Comparator<String> {
 public String sortChars(String s) {
   char[] content = s.toCharArray();
   Arrays.sort(content);
   return new String(content);
 }

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

Но мне интересно, как можно было бы реализовать это в C++? Кодирование эквивалента C++ встроенных методов, используемых в приведенном выше коде Java, безусловно, является одним из вариантов. Есть ли другой разумный способ?

Answer 1

Двухуровневый подход:

Сортировать строку s в отсортированную строку tи добавить запись в map<string, vector<string> как m[t].push_back(s);, Тогда каждая запись карты является вектором взаимно анаграмматических строк.

Вы можете реализовать ту же логику в одном плоском мультикарте, но это будет намного дороже (поскольку вам придется каждый раз сортировать строку); или вы можете создать компаратор, который лексикографически сравнивает отсортированную строку сначала и фактическую строку вторую, но опять же это очень дорого.

Answer 2

Очевидный, а также лучший способ очень похож на тот, который вы выбрали в Java: реализовать собственный компаратор.

В C++ это специализация предиката меньше чем:

struct less_than_sorted_anagram {
    bool operator ()(std::string a, std::string b) {
        std::sort(a.begin(), a.end());
        std::sort(b.begin(), b.end());
        return a < b;
    }
};

И назовите это так:

std::vector<std::string> range;
// …
std::sort(range.begin(), range.end(), less_than_sorted_anagram());

Но (как и ваш Java-код) это довольно неэффективно, поскольку отсортированные анаграммы необходимо вычислять повторно. Было бы намного эффективнее вычислять их только один раз (скажем, при первом использовании) и кэшировать их.

Вы можете, например, сохранить этот кэш внутри less_than_sorted_anagram предикат как std::map<std::string, std::string> (или подобный словарь, отображающий строки в строки).