Технический журнал
Проблема LeetCode 2744.
24 июля 2023 г.
Аксель Давид Гарсия Бельтран
Обзор
В этом документе мы рассмотрим задачу LeetCode #2744, которая заключается в поиске пар строк-палиндромов в данной коллекции. Мой подход — это простая итерация по массиву, однократное сравнение каждой строки со всеми остальными и подсчет допустимых пар. Это решение имеет временную сложность O(n2), но может быть улучшено до линейного времени с помощью соответствующей структуры данных.
Контекст
Это проблема LeetCode 2744. Найдите максимальное количество пар строк. Пожалуйста, перейдите по ссылке, чтобы попрактиковаться и посмотреть обсуждение в сообществе.
В этой задаче нам дан набор слов из различных строк. От нас требуется найти допустимые пары строк и подсчитать их, вернув максимальное количество, которое мы найдем. Чтобы пара строк str1 и str2 считалась действительной, она должна удовлетворять 3. требованиям:
- str1 должен быть равен str2 в обратном порядке символов. Из-за рефлексивности это эквивалентно утверждению, что str2 должна быть равна перевернутой str1.
- Если words[i] = str1 и words[j] = str2, то 0 ‹ i ‹ j ‹ words.length.
- Ни str1, ни str2 не должны были быть соединены ранее.
Ввод, вывод
- Ввод: массив слов с индексом 0, состоящий из отдельных строк.
- Вывод: целое число n с максимальным количеством допустимых пар, которые могут быть сформированы из слов массива.
Решение
Первоначальная идея
Мое решение довольно простое, но интуитивно понятное. Что мы хотим сделать, так это пройтись по заданному массиву и сравнить каждую строку с другими. Однако нам не нужно сравнивать уже увиденные строки. Итак, мы можем использовать два указателя, i и j, для сравнения пар строк. я бы прошел весь массив, а j сравнил бы только то, что находится перед i. Нам также нужно отслеживать уже спаренные строки; мы можем использовать логический массив для сохранения индексов уже посещенных строк.
Алгоритм
Далее следует алгоритм моего решения в псевдокоде. Это можно реализовать на любом известном языке программирования, от Python до C и The Game of Life:
maximumNumberOfStringPairs(words) returns int pairs -> 0
from i -> 0 to words.length
if visited[i] = true then
next iteration
from i to n
if visited[j] then
next iteration
if words[I] = reverse(words[j]) then
pairs -> pairs + 1
visited[i], visited[j] -> true
return pairs
В качестве примера вот ссылка с конкретной реализацией этого алгоритма на Java.
Альтернативные решения
Этот алгоритм, хотя и простой, имеет временную сложность O(n2), где n — длина заданного массива. Однако при эффективном использовании структур данных, таких как HashSet вместо массива для отслеживания посещенных строк, эта проблема может быть решена за линейное время. Также важно отметить, что этот алгоритм зависит от определения метода reverse(), и поэтому его конкретная реализация может повлиять на общую сложность.
