Продолжаем разбор задач с Yandex Cup 2023 для бэкендеров.
Первая часть здесь - https://habr.com/ru/articles/772748.
Вторая задача - Хокку на английском (описание под катом).
Hidden text
Поэт пытается освоить жанр традиционной японской лирической поэзии — хокку. Он мечтает писать хокку на японском языке. К его большому сожалению, изучение японского даётся ему слишком тяжело. Поэтому он тренируется писать хокку на английском.
Такой жанр поэзии требует математической гармонии в сложении звуков, слов и смыслов. Поэт уверен, что создать по-настоящему совершенное хокку на английском языке он сможет только с помощью человека с техническим складом ума. Он обращается к вам за помощью.
У поэта есть для вас правило, на основе которого вам нужно написать функцию. Он приготовил для вас строку s. Строка состоит из строчных и заглавных букв английского алфавита.
Вам предстоит изменить в строке наименьшее количество символов так, чтобы:
в s встречалась подстрока Yandex (регистр имеет значение).
в s встречалась подстрока Cup (регистр имеет значение).
хотя бы для одной пары подстрок Yandex и Cup, первым шло слово Yandex.
Ваша задача: вывести строку после замены символов и помочь поэту создать совершенное хокку на английском языке.
Формат ввода:
Входные данные содержат строку s (9 ≤ |s| ≤ 1 000 000).
Формат вывода:
Выведите строку после замены символов. Результирующая строка должна содержать только строчные и заглавные буквы английского алфавита, при этом количество измененных символов должен быть минимально возможным.
Если подходящих под условие задачи строк несколько, то выведите любую из них.
Пример 1:
Ввод: yandexcup
Вывод: YandexCup
Пример 2:
Ввод: cupyandex
Вывод: YandexCup
Пример 3:
Ввод: YandexYetAnotherCup
Вывод: YandexYetAnotherCup
Пример 4:
Ввод: YanCupdex
Вывод: YandexCup
Пример 5:
Ввод: salkdfjhdskfgpsajdhfgk
Вывод: YandexjhdskCupsajdhfgk
В задаче про хокку смущает, что она совсем не про хокку.
Если в первых примерах можно просто найти подстроку через s.toLowerCase().indexOf("yandex”), то в 4 и 5 примерах нужно делать более сложный перебор искомых слов и строки ввода.
Сначала объявляем переменные и считываем строку:
final String YANDEX = "Yandex";
final String CUP = "Cup";
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine();
StringBuilder stringBuilder = new StringBuilder(input);Далее проверяем, если в строке есть слова Yandex и Cup в такой последовательности, то возвращаем строку без изменений. А также меняем последовательность при необходимости и выводим результат:
if (input.contains(YANDEX) && input.contains(CUP)) {
if (input.indexOf(YANDEX) < input.indexOf(CUP)) {
System.out.println(input);
} else if (input.indexOf(YANDEX) > input.indexOf(CUP)) {
int cupIndex = stringBuilder.indexOf(CUP);
int yandexIndex = stringBuilder.indexOf(YANDEX);
String yandexCup = stringBuilder.substring(0, cupIndex)
+ YANDEX
+ stringBuilder.substring(cupIndex + CUP.length(), yandexIndex)
+ CUP
+ stringBuilder.substring(yandexIndex + YANDEX.length());
System.out.println(yandexCup);
}
}Далее проверяем, если в строке нет искомых слов, то нужно с минимальными заменами вставить искомые слова. Для этого нужно вычислить минимальное количество замен через перебор с каким-нибудь аккумулирующим счетчиком.
else {
int yandexLength = YANDEX.length();
int cupLength = CUP.length();
int maxMatches = 0;
int bestMatchIndex = 0;
int yandexLastIndex = YANDEX.length();
//best matches for Yandex
for (int i = 0; i < input.length() - (yandexLength + cupLength); i++) {
int currentMatches = 0;
for (int j = 0; j < yandexLength; j++) {
if (input.charAt(i + j) == YANDEX.charAt(j)) {
currentMatches++;
}
}
if (currentMatches > maxMatches) {
maxMatches = currentMatches;
bestMatchIndex = i;
yandexLastIndex = i + YANDEX.length();
}
}
stringBuilder.replace(bestMatchIndex, bestMatchIndex + yandexLength, YANDEX);
//best matches for Cup
maxMatches = 0;
bestMatchIndex = 6;
for (int i = yandexLastIndex; i < input.length() - cupLength; i++) {
int currentMatches = 0;
for (int j = 0; j < cupLength; j++) {
if (input.charAt(i + j) == CUP.charAt(j)) {
currentMatches++;
}
}
if (currentMatches > maxMatches) {
maxMatches = currentMatches;
bestMatchIndex = i;
}
}
stringBuilder.replace(bestMatchIndex, bestMatchIndex + cupLength, CUP);
System.out.println(stringBuilder.toString());
}В цикле "best matches for Yandex" проверяем строку с первого символа и на каждой итерации запускаем цикл из 6 проверок на соответствие символа одной из последующих букв в слове Yandex. По итогу получаем индекс (bestMatchIndex), с которого сделаем замену с помощью stringBuilder-а.
Далее повторяем такой же цикл в "best matches for Cup", одновременно обнуляя maxMatches и сдвигая bestMatchIndex на 6 (количество букв Yandex). Снова делаем замену с помощью stringBuilder-а и выводим результат.
В итоге, каждый пример из задачи выдает правильный результат.
