Задача

Два слова называются анаграмматически одинаковыми, если из букв одного слова можно получить другое слово. Например, occurs является анаграммой для слова succor; и наоборот, dear не является анаграммой слова dared (так как буква d встречается дважды в dared, и только один раз в dear). Наиболее известной английской анаграммой являются слова dog и god.

Анаграмматическим расстоянием двух слов называется минимальное количество букв, которые нужно удалить, чтобы в результате два слова стали анаграмматически одинаковыми. Например, для слов sleep и leap, нужно удалить как минимум три буквы — две из sleep и одну из leap — чтобы остались анаграмматически одинаковые слова (в указанном случае lep). А для слов dog и cat, в которых нет одинаковых букв, анаграмматическое расстояние равно $6$, так как нужно удалить все буквы. (Любое слово, в том числе и пустая строка, являются анаграммой само к себе.)

Ваша задача найти анаграмматическое расстояние для заданных двух слов.

Входные данные

В первой строке задано положительное целое число $N$ (не превышающее $60000$), указывающее количество тестовых примеров. Каждый тестовый пример состоит из двух слов, возможно пустых, каждое из которых записано в отдельной строке (всего $2N$ последующих строк).

Все слова, имеющие не нулевую длину, сформированы из строчных букв английского алфавита (abcdefghijklmnopqrstuvwxyz). Самым длинным словом является pneumonoultramicroscopicsilicovolcanoconiosis.

Выходные данные

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

Тесты

Входные данные	Выходные данные
4 crocus succor dares seared empty smell lemon	Case #1: 0 Case #2: 1 Case #3: 5 Case #4: 4
3 dog god cat dog dragon fly	Case #1: 0 Case #2: 6 Case #3: 9
1 cow	Case #1: 3
1 memory moratory	Case #1: 6

Код программы

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
	public static void main (String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		final int ABC_SIZE = 26;
		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			int[] counters = new int[ABC_SIZE];
			String firstWord = br.readLine();
			for (int j = 0; j < firstWord.length(); j++) {
				counters[firstWord.charAt(j) - 'a']++;
			}
			String secondWord = br.readLine();
			for (int j = 0; j < secondWord.length(); j++) {
				counters[secondWord.charAt(j) - 'a']--;
			}
			int matchingLetters = 0;
			for (int k = 0; k < ABC_SIZE; k++) {
				matchingLetters += Math.abs(counters[k]);
			}
			System.out.println("Case #" + (i + 1) + ":  " + matchingLetters);
		}
		
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

public class Main {

public static void main (String[] args) throws Exception{

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

final int ABC_SIZE = 26;

int n = Integer.parseInt(br.readLine());

for (int i = 0; i < n; i++) {

int[] counters = new int[ABC_SIZE];

String firstWord = br.readLine();

for (int j = 0; j < firstWord.length(); j++) {

counters[firstWord.charAt(j) - 'a']++;

}

String secondWord = br.readLine();

for (int j = 0; j < secondWord.length(); j++) {

counters[secondWord.charAt(j) - 'a']--;

}

int matchingLetters = 0;

for (int k = 0; k < ABC_SIZE; k++) {

matchingLetters += Math.abs(counters[k]);

}

System.out.println("Case #" + (i + 1) + ": " + matchingLetters);

}

Решение

Создадим массив на $26$ элементов, соответствующих буквам латинского алфавита. Для каждой буквы первого слова будем увеличивать на $1$ соответствующий ей элемент, а для каждой буквы второго слова — уменьшать. В конце, полученные значения будут указывать на то, сколько в первом слове «лишних» букв по сравнению со вторым (и наоборот, в случае отрицательных значений). Сумма абсолютных значений элементов массива и будет являться анаграмматическим расстоянием для указанных слов.

Ссылки

Условие задачи на e-olymp
Решение на ideone
Решение на e-olymp

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: слово

e-olymp 1080. Анаграмматическое расстояние