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

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

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

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

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

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

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

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

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

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

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

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

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

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

Бенчмарк на TypeScript

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

Бенчмарк на JavaScript

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

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

Задача следующей комбинации (next permutation)

Март 13, 2023 г.

Мне понадобилось какое то время, чтобы понять верный подход к решению, делюсь подробным разбором этой задачи. Ставится она так: есть набор (массив) элементов, чаще всего чисел, требуется найти следующей по порядку возрастания набор этих элементов. ...

Читать

Задача: подсчета кол-ва возможных маршрутов

Июнь 25, 2023 г.

Решаем задачу с литкода №1575 Count All Possible Routes. Дан массив чисел, описывающий города. Указаны индексы стартового города (start) и города, куда нужно приехать (finish), а также запас топлива (fuel). Требуется найти кол-во путей, по которым ...

Читать

 

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

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



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