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

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

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

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

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

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

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

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

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

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

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

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

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

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

Бенчмарк на TypeScript

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

Бенчмарк на JavaScript

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

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

Задача - число островов

Март 25, 2023 г.

Разбираю задачу #200 с литкода, число островов (number of islands). Задан двумерный массив, в котором участки суши помечены как "1", а участки воды - как "0". Требуется подсчитать число получившихся островов. При этом считается, что участки суши образуют ...

Читать

TS: функция преобразования к каноническому пути

Март 15, 2023 г.

Увидел эту задачу на leetcode - https://leetcode.com/problems/simplify-path/, где не так часто встречаются задачи близкие к практиктическому программированию. Ранее уже приводил решение подобной задачи для PHP. Здесь порешаем её уже на TS. Задача ...

Читать

 

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

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



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