Матч 391, Изоморфные слова (IsomorphicWords)

Дивизион 2, Уровень 2

Два слова называются изоморфными, если буквы одного слова можно взаимно однозначно отобразить на буквы другого. Отображением называется замена всех вхождений одной буквы на другую. Порядок следования букв после отображения должен быть сохранен. Буква может отображаться сама на себя. В массиве строк words требуется подсчитать количество неупорядоченных пар изоморфных слов.

Класс: IsomorphicWords

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

Ограничения: words содержит от 2 до 50 строк, каждая из которых содержит от 1 до 50 прописных букв латинского алфавита (нижнего регистра), все слова массива words имеют одинаковую длину, массив words не содержит одинаковых слов.

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

Выход. Количество неупорядоченных пар изоморфных слов в массиве words.

Пример входа

words

{"abca", "zbxz", "opqr"}

{"aa", "ab", "bb", "cc", "cd"}

{ "cacccdaabc", "cdcccaddbc", "dcdddbccad", "bdbbbaddcb",

"bdbcadbbdc", "abaadcbbda", "babcdabbac", "cacdbaccad",

"dcddabccad", "cacccbaadb", "bbcdcbcbdd", "bcbadcbbca" }

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

1

4

13

РЕШЕНИЕ

обработка массивов

Функция Isomorphic проверяет, являются ли два входных слова a и b изоморфными. Заведем два линейных массива _map и _remap длины 256, для которых _map[i] содержит букву строки b, на которую отображается a[i], а _remap[i] содержит букву строки a, которая отображается на b[i]. Для каждого i (0 £ i £ a.size()) должны выполняться соотношения:

_map[a[i]] = b[i], _remap[b[i]] = a[i]

Если для какого-нибудь i равенства не выполняются, то слова a и b не изоморфны.

Перебираем все пары слов массива words, и подсчитываем количество изоморфных слов при помощи функции Isomorphic.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

#include <string>

using namespace std;

int Isomorphic(string a, string b)

{

vector<char> _map(256,-1),_remap(256,-1);

for(int i = 0; i < a.size(); i++)

{

if ((_map[a[i]] == -1) && (_remap[b[i]] == -1))

_map[a[i]] = b[i], _remap[b[i]] = a[i];

if ((_map[a[i]] != b[i]) || (_remap[b[i]] != a[i])) return 0;

}

return 1;

}

class IsomorphicWords

{

public:

int countPairs(vector<string> words)

{

int i, j, c;

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

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

if (Isomorphic(words[i],words[j])) c++;

return c;

}

};