Матч 402, Аббревиатура слов (WordAbbreviation)

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

Имеется массив строк words, содержащий набор слов. Необходимо вернуть массив, i - ый элемент которого является аббревиатурой i - го слова. Аббревиатурой слова является наименьший непустой префикс, не являющийся префиксом никакого другого слова. Аббревиатура слов всегда существует.

Класс: WordAbbreviation

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

Ограничения: words содержит от 1 до 50 строк, каждая из которых содержит от 1 до 50 символов ‘a’ – ‘z’, ни одно из слов не является префиксом другого.

Вход. Массив строк words, содержащий набор слов.

Выход. Массив, i - ый элемент которого является аббревиатурой i - го слова.

Пример входа

Words

{"abc","def","ghi"}

{"aaab","aaac","aaad"}

{"top","coder","contest"}

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

{"a", "d", "g"}

{"aaab", "aaac", "aaad"}

{"t", "cod", "con"}

РЕШЕНИЕ

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

Перебираем слова в цикле по i. Для каждого слова в цикле по j перебираем его префиксы str, начиная с наименьшего. В цикле по k проверяем, не является ли слово str префиксом какого-нибудь другого слова. Если после выполнения цикла по k значение flag равно 1 (str является лишь префиксом одного слова, из которого оно порождено), то аббревиатура слова найдена и заносится в результирующий массив res.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

using namespace std;

class WordAbbreviation

{

public:

vector<string> getAbbreviations(vector<string> words)

{

int i,j,k,flag;

vector<string> res;

string str;

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

{

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

{

str = words[i].substr(0,j);

for(flag = k = 0; k < words.size(); k++)

if (words[k].substr(0,str.size()) == str) flag++;

if (flag == 1) break;

}

res.push_back(str);

}

return res;

}

};