どのようにアナグラムがC++でお互いに近いように文字列をソートしますか？

Question

それはあなたがコンパレータを使用して、文字配列をソートし、このような文字列を比較する方法で構築された可能性があるので、Javaで実装するのは本当になりたい：

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

しかし、私はどのように1を約行くと思ったんだけどこれをC++で実装していますか？ 上記のJavaコードで使用されている組み込みメソッドと同等のC++コード化は、間違いなく1つのオプションです。他のインテリジェントな方法はありますか？

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

そして、このようにそれを呼び出します（ちょうどあなたのJavaコードのような）

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

しかし、これは、以来、非常に非効率的ですソートされたアナグラムを繰り返し計算する必要があります。一度だけ（一回目の使用時に）それらを計算し、それらをキャッシュする方がはるかに効率的です。

たとえば、less_than_sorted_anagram述部内でこのキャッシュをstd::map<std::string, std::string>（または文字列に文字列をマッピングする同様の辞書）として維持することができます。