Как бы вы отсортировали строки так, чтобы анаграммы были близки друг к другу в 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

Очевидный, а также лучший способ очень похож на тот, который вы выбрали в 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> (или аналогичный словарь, отображающий строки в строки).

Answer 2

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

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

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