2

Comparator と組み込みメソッドを使用して文字配列をソートし、次のように文字列を比較できるため、実際には 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));
 }
}

しかし、これを C++ で実装するにはどうすればよいのでしょうか。上記の Java コードで使用される組み込みメソッドに相当する C++ をコーディングすることは、間違いなく 1 つのオプションです。他に賢明な方法はありますか？

4

2 に答える 2

5

明白で最良の方法は、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 コードと同様に) ソートされたアナグラムを繰り返し計算する必要があるため、これは非常に非効率的です。それらを 1 回だけ (最初の使用時などに) 計算してキャッシュする方がはるかに効率的です。

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

于 2012-01-24T13:59:14.217 に答える
1

2 レベルのアプローチ:

文字列sをソート済み文字列にソートし、 astにエントリを追加します。次に、マップの各エントリは、相互にアナグラム的な文字列のベクトルです。map<string, vector<string>m[t].push_back(s);

同じロジックを単一のフラット マルチマップに実装することもできますが、その場合ははるかにコストがかかります (毎回文字列を並べ替える必要があるため)。または、ソートされた文字列を最初に辞書式に比較し、次に実際の文字列を比較するコンパレータを作成することもできますが、これも非常に高価です。

于 2012-01-24T13:59:42.227 に答える