0

基本的に、単語に一致するすべてのアナグラムを見つける必要があります。私が行っていたのは、サイズ 26 の配列を使用して単語の文字を表すことでした。元：

abcdefg={1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
aaaaaaa={7,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

これが私が配列を作成している方法です。

//stringtemp is a C++ string representing the word.
//letters is a size 26 int array representing all the letters in the string.
for(int i=0;i<stringtemp.length();i++)
{
    letters[stringtemp[i]-65]+=1;
}

そして、これが配列をマップに格納する方法です。

dictionary[letters].push_back(stringtemp);

それで、私は何か間違ったことをしていますか、それとも C++ では不可能ですか。私が見つけた他のすべての回答では、ベクトルをキーとして使用することを提案しましたが、それは私の場合はうまくいきません(私は思う.)

4

3 に答える 3

9

とのすべてはstd::array<T, 26>、a に対して完全に有効なキー タイプです。これらはすべて、より小さい比較演算子を定義しているためです。は に似ており、比較は辞書式に定義されており、文字列比較に非常に似ていることに注意してください。std::stringstd::vector<T>std::mapstd::array<T, 26>std::tuple<T, T, ..., T>

#include <array>
#include <map>

typedef std::array<unsigned int, 26> alphabet;

std::map<alphabet, std::string> dictionary;

dictionary[{{1, 0, ..., 8}}] = "hello";

もう少し作業すれば、これらすべての型のキーを にすることもstd::unordered_mapできますが、Boost から定型コードを少し追加する必要があります ( を使用hash_combine)。

于 2012-09-15T15:29:11.960 に答える
2

std::mapを使用すると、コンストラクターで Compare 演算子を提供できます。2 つの配列 {1,....} と {1,....} を一致させるには、これらが異なる実際のオブジェクトである可能性があるため、このような Comparator を提供する必要がある場合があります。

于 2012-09-15T15:29:49.273 に答える
1

マップのキー タイプには、 がoperator<定義されている必要があります。配列型を定義することもできますoperator<が、もっと簡単な方法があります。各単語の文字をアルファベット順に並べ替え、その並べ替えられた文字列をキーとして使用します。

于 2012-09-15T15:29:03.600 に答える