Это решение sherlockAndAnagrams, которое я придумал по рангу хакеров. Цель состоит в том, чтобы найти количество соответствующих анаграмм подстроки в строке. Например, у "abba" будут анаграммы, ["a", "a"], ["ab", "ba"], ["abb", "bba"], ["b", "b"].
Чтобы решить эту проблему, я пытаюсь создать двоичную карту, чтобы использовать массив в качестве ключа. Тем не менее, функция компаратора, которую я написал, не в состоянии перехватить каждый контрольный пример. Для примера, который я дал ранее ("abba"), он находит все совпадения, за исключением того, что он не соответствует ["b", "b"].
Есть ли что-то, что я неправильно понимаю в функциональности компаратора? Я считаю, что это удовлетворяет строгому слабому порядку.
struct cmpByArray {
bool operator()(const array<unsigned int, 26>& a, const array<unsigned int, 26>& b) const {
for(size_t i=0; i<a.size(); i++)
{
if(a[i] < b[i])
return true;
}
return false;
}
};
int sherlockAndAnagrams(string s) {
int matches = 0;
map< array<unsigned int, 26>, int, cmpByArray> m1;
for(size_t i=0; i<s.length(); i++)
{
cout << s[i] << std::endl;
for(size_t j=i; j<s.length(); j++)
{
cout << '-';
array<unsigned int, 26> arr = {0};
for(size_t k=i; k<=j; k++)
{
cout << s[k];
arr[s[k]-'a']++;
}
cout << endl;
if( m1.find(arr) != m1.end())
{
matches++;
cout << "match: " << endl;
}
else
{
m1[arr]++;
}
}
}
return matches;
}