Task 28. Строки "близнецы"
UniLecsЗадача: две строки можно сделать одинаковыми, выполняя определенное количество операций перестановок символов над одной или обеими строками.
Возможны следующие операции:
1. SwapEven: обмен символом с индексом с четным номером с символом в другом индексе с четным номером.
2. SwapOdd: обмен символом с индексом с нечетным номером с символом в другом индексе с нечетным номером.
Например, строки "abcd", "cdab" можно сделать одинаковыми, переставив символы:
- "c" (символ с нечетным индексом 1) / "a" (символ с нечетным индексом 3)
- "d" (символ с четным индексом 2) / "b" (символ с четным индексом 4)
В другому примере строки "abcd", "bcda" нельзя сделать одинаковыми, т.к. например символ "a" в первом слове стоит на нечетном индексе (1), во втором слове на четном (4).
Написать функцию, ктр проверит возможно ли сделать две строки одинаковыми.
Идея: есть несколько вариантов и подходов для решения такой задачи, разберем один из них.
Для этого разложим каждую строку в следующем формате:
все отсортированные символы, ктр стоят на четном индексе + все отсортированные символы, ктр стоят на нечетном индексе.
Дальше мы просто сравним преобразованные две преобразованные строки, если они совпадают, то исходные две строки можно сделать одинаковыми.
Общий алгоритм будет таким:
1. Формируем два массива c "четными"/"нечетными" символами.
2. Сортируем оба массива.
3. Формируем закодированную строку: все отсортированные "четные" символы + все отсортированные "нечетные" символы.
4. Сравниваем закодированные строки исходных строк. Profit!
Реализация:
https://gist.github.com/unilecs/186d8559a07bc8adb75a1b244498e048