Условия задачи
Два слова называются анаграмматически одинаковыми, если из букв одного слова можно получить другое слово. Например, occurs является анаграммой для слова succor; и наоборот, dear не является анаграммой слова dared (так как буква d встречается дважды в dared, и только один раз в dear). Наиболее известной английской анаграммой являются слова dog и god.
Анаграмматическим расстоянием двух слов называется минимальное количество букв, которые нужно удалить, чтобы в результате два слова стали анаграмматически одинаковыми. Например, для слов sleep и leap, нужно удалить как минимум три буквы — две из sleep и одну из leap — чтобы остались анаграмматически одинаковые слова (в указанном случае lep). А для слов dog и cat, в которых нет одинаковых букв, анаграмматическое расстояние равно [latex]6[/latex], так как нужно удалить все буквы (любое слово, в том числе и пустая строка, являются анаграммой само к себе).
Ваша задача найти анаграмматическое расстояние для заданных двух слов.
Входные данные
В первой строке задано положительное целое число [latex]N[/latex] (не превышающее [latex]60000[/latex]), указывающее количество тестовых примеров. Каждый тестовый пример состоит из двух слов, возможно пустых, каждое из которых записано в отдельной строке (всего [latex]2N[/latex]последующих строк).
Все слова, имеющие не нулевую длину, сформированы из строчных букв английского алфавита (abcdefghijklmnopqrstuvwxyz). Самым длинным словом является pneumonoultramicroscopicsilicovolcanoconiosis.
Выходные данные
Для каждого примера входных данных вывести в отдельной строке номер тестового случая и анаграмматическое расстояние, отформатированные так, как показано в примере выходных данных.
Ссылка на задачу находится здесь.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 4 crocus succor dares seared empty smell |
Case #1: 0 Case #2: 1 Case #3: 5 Case #4: 4 |
| 2 | 1
|
Case #1: 0 |
| 3 | 5 lol lolipop primate mathematics kangaroo kilimanjaro sister sisters android andromeda |
Case #1: 4 Case #2: 8 Case #3: 7 Case #4: 1 Case #5: 4 |
Код (cstring)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <cstring> #include <iostream> using namespace std; const short maxSize = 46; int main() { int n, matchingLetters; cin >> n; cin.ignore(); char *word_1 = new char[maxSize]; char *word_2 = new char[maxSize]; for (int i = 0; i < n; i++) { matchingLetters = 0; cin.getline(word_1, maxSize); cin.getline(word_2, maxSize); for (int j = 0; j < strlen(word_1); j++) { for (int k = 0; k < strlen(word_2); k++) { if (word_1[j] == word_2[k]) { word_2[k] = '#'; matchingLetters++; break; } } } cout << "Case #" << i + 1 << ": " << strlen(word_1) + strlen(word_2) - 2 * matchingLetters << endl; } return 0; } |
Код на ideone можно найти здесь.
Ход решения
Наша задача состоит в определении количества символов в двух строках, которые необходимо удалить для того, чтобы слова считались анаграммами. Используем после ввода числа примеров [latex]n[/latex] функцию cin.ignore(), для игнорирования перехода на новую строку, а затем считываем по парам слова. Последовательно проходим все буквы слова в первой строке с помощью цикла for. Если находим эту букву в слове второй строки, увеличиваем счётчик совпадающих букв. Совпадающую букву во второй строке заменяем на символ #, дабы избежать повторных проверок одной и той же буквы в случае её неоднократного появления в первой строке. Общее количество букв в двух строках равняется сумме длин первой и второй строк. Таким образом, чтобы получить анаграмматическое расстояние необходимо вывести:
|
26 |
strlen(word_1) + strlen(word_2) - 2 * matchingLetters |
Умножение matchingLetters на [latex]2[/latex] возникает вследствие того, что (по факту) нужно зачёркивать символы в двух строках.
Стоит отметить, что в задаче не требуется реализовывать поиск символа самостоятельно. Можно воспользоваться уже встроенной функцией для работы со строками strchr(), которая вернёт нам указатель на искомый символ. Если символ не будет найден, функция вернёт NULL. Тогда наш код приобретает следующий вид:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <cstring> #include <iostream> using namespace std; const short maxSize = 46; int main() { int n, matchingLetters; cin >> n; cin.ignore(); char *word_1 = new char[maxSize]; char *word_2 = new char[maxSize]; for (int i = 0; i < n; i++) { matchingLetters = 0; cin.getline(word_1, maxSize); cin.getline(word_2, maxSize); for (int j = 0; j < strlen(word_1); j++) { if (strchr(word_2, word_1[j])) { *strchr(word_2, word_1[j]) = '#'; matchingLetters++; } } cout << "Case #" << i + 1 << ": " << strlen(word_1) + strlen(word_2) - 2 * matchingLetters << endl; } return 0; } |
Код на ideone можно найти здесь.
Код (string)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <string> #include <iostream> using namespace std; int main() { int n, matchingLetters; cin >> n; cin.ignore(); string word_1, word_2; for (int i = 0; i < n; i++) { matchingLetters = 0; getline(cin, word_1); getline(cin, word_2); for (int j = 0; j < word_1.size(); j++) { if (word_2.find(word_1[j]) != string::npos) { word_2[word_2.find(word_1[j])] = '#'; matchingLetters++; } } cout << "Case #" << i + 1 << ": " << word_1.size() + word_2.size() - 2 * matchingLetters << endl; } return 0; } |
В случае решения данной задачи с помощью класса string используем функцию find() для поиска заданного символа в строке.
Код на ideone можно найти здесь.
Ссылка на засчитанное решение.