Матч 432, Группированные слова (GroupedWordChecker)

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

Слово называется группированным, если для каждой его буквы все ее появления в слове образуют в точности одну последовательность. То есть никакие две одинаковые буквы не разделяются другими. Например, слова “ccazzzzbb” и “code” являются группированными, а “aabbbccb” и “topcoder” нет. Необходимо подсчитать количество группированных слов в массиве words.

Класс: GroupedWordChecker

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

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

Вход. Массив слов words.

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

Пример входа

words

{"ccazzzzbb", "code", "aabbbccb", "topcoder"}

{"ab", "aa", "aca", "ba", "bb"}

{"yzyzy", "zyzyz"}

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

2

4

0

РЕШЕНИЕ

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

Функция Grouped проверяет, является ли слово s группированным. Заведем массив w, в котором положим w[i] = 1, если буква ‘a’ + i в слове уже встречалась. Далее просто подсчитываем количество группированных слов.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <memory>

using namespace std;

int Grouped(string s)

{

int i, w[26];

memset(w,0,sizeof(w));

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

{

if (w[s[i] - 'a'] > 0) return 0;

w[s[i] - 'a'] = 1;

while((i + 1 < s.size()) && (s[i] == s[i+1])) i++;

}

return 1;

}

class GroupedWordChecker

{

public:

int howMany(vector<string> words)

{

int i,res;

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

if (Grouped(words[i])) res++;

return res;

}

};