TCHS 08, Раунд 3, Подобные слова (SimilarWords)

Подобностью двух слов будем называть количество в них общих букв. Буквы сравниваются без учета регистра. Если некоторая буква встречается в одном слове k раз, а в другом m раз, то в подобность слов эта буква вносит значение min(k, m).

Массив words содержит набор слов. Необходимо найти два слова с наибольшим значением подобия и вернуть его.

Класс: SimilarWords

Метод: int mostSimilarPair(vector<string> words)

Ограничения: words содержит от 2 до 50 элементов, words[i] содержит от 1 до 50 символов ‘a’ – ‘z, ‘A’ – ‘Z’.

Вход. Массив строк words.

Выход. Наибольшее значение подобия двух слов из массива words.

Пример входа

words

{"aaB", "AbaAc"}

{"abcdefg","ABCDEFG"}

{"alnHFDfosKYFREanfETRiesf", "fjsHDdoAFifASsd",

"GSDgsdGsdgJUsg", "KJmgnsNSFsngfn", "njtdhMHGBSmnytgnGVNR"}

Пример выхода

3

7

11

РЕШЕНИЕ

обработка строк

Для каждой пары слов a и b вычисляем их подобие при помощи функции similar(a, b). Наибольшее значение подобия возвращаем.

Опишем работу функции similar(a, b). В отображении m1 подсчитываем, сколько раз встречается каждая буква строки a. В m2 подсчитываем буквы строки b. При подсчете все буквы переводим в нижний регистр. Например, значение m1[x] содержит значение, равное количеству малых и больших букв x в строке a. Далее проходим по отображению m1 при помощи итератора iter. Значение (*iter).first равно букве из строки a, а (*iter).second равно количеству раз, которое она встречается в a. Тогда m2[(*iter).first] равно количеству раз, которое эта буква встречается в b. Поэтому для нахождения подобия слов следует просуммировать значения min((*iter).second, m2[(*iter).first]).

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <map>

using namespace std;

int similar(string a, string b)

{

int i,res;

map<char,int> m1,m2;

map<char,int>::iterator iter;

m1.clear();m2.clear();

for(res=i=0;i<a.size();i++) m1[tolower(a[i])]++;

for(i=0;i<b.size();i++) m2[tolower(b[i])]++;

for(iter=m1.begin();iter!=m1.end();iter++)

res += min((*iter).second,m2[(*iter).first]);

return res;

}

class SimilarWords

{

public:

int mostSimilarPair(vector<string> words)

{

int i,j,temp,res;

for(res=i=0;i<words.size()-1;i++)

for(j=i+1;j<words.size();j++)

{

temp = similar(words[i],words[j]);

if (temp > res) res = temp;

}

return res;

}

};