Задача группировки подобных строк

Речь идет о № 839 с leetcode.

Формулируется проблема таким образом — дан массив строк, которые отличаются (или не отличаются) друг от друга перестановкой букв. Подобными считаются 2 строки, отличающиеся друг от друга только одной перестановкой или равные друг другу.

При этом если строка 1 подобна строке 2, а строка 2 подобна строке 3, то все три должны попасть в одну группу подобия. Хотя строка 1 может не быть подобна строке 3.

Результатом является кол-во групп подобия.

Во-первых, как определить подобность?

Если мы сравним две строки, то результат одной перестановки приведет к тому, что у нас появится несовпадение по двух буквам. Т.е. подобными будут строки с 2 отличиями или равные.

Во-вторых, что можно оптимизировать?

По сути, нам нужно сравнить все строки друг с другом, чтобы определить их принадлежность к группам. Т.е. это вложенный цикл попарных сравнений, которых нам не избежать. Нам не требуется сравнивать строки, только если они уже принадлежат к одной и той же группе. Например если мы сравнивали строки 1 и 2, а потом 1 и 3, и оказалось что они подобны, то строку 2 и 3 уже сравнивать не надо.

Нам понадобится для каждой строки где то отмечать информацию: к какой группе она принадлежит — у меня это будут одномерный массив grp.

Может выясниться, что подобными являются строки из уже известных групп. В таком случае нужно будет объединить две группы.

Собираю все мысли воедино, и вот что вышло (TypeScript):

Задача отмечена как hard, и наверное, можно придумать как её решать «сложным» способом, например динамическим алгоритмом или рекурсивно в том или ином виде, но я что то не придумал такого варианта. А моё решение, наверное, больше подходит для средней сложности задач.

Тем не менее, задача решена, и судя по бенчмаркам leetcode — весьма хорошо. К сожалению, на TS у меня нет конкурентов, чтобы оценить.

Бенчмарк на TypeScript

Потому я решил переписать её на JS, и сравнить результаты там. Как видите, всё отлично и тут.

Бенчмарк на JavaScript

Написать комментарий

Мало букафф? Читайте есчо !

Решение задачи оптимизации в направленном графе

Апрель 9, 2023 г.

Сегодня расскажу о решении задачи №1857 с литкода, которая называется как "Largest Color Value in a Directed Graph". Суть задачи: дан направленный ...

Читать

Задача о поиске всех подходящих под-сум

Июль 1, 2023 г.

№560 leetcode Subarray Sum Equals K. Есть массив чисел, и дано значение k. Надо найти все последовательные под-массивы сумма которых равна k. В условиях также сказано, что числа в массиве могут быть как положительные, так и отрицательные. Если ...

Читать

 

Комментарии к «Задача группировки подобных строк»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: