Пример:
Учитывая список уникальных слов, найдите все пары различных индексов (i, j) в данном списке, чтобы конкатенация двух слов, то есть слова [i] + слова [j], была палиндром.
Пример 1:
Данные слова = [«летучая мышь», «вкладка», «кошка»]
Вернуть [[0, 1], [1, 0]]
Палиндромы [«баттаб», «таббат»]
Пример 2:
Даны слова = [«abcd», «dcba», «lls», «s», «sssll»]
Вернуть [[0, 1], [1, 0], [3, 2], [2, 4]]
Палиндромы: [«dcbaabcd», «abcddcba», «slls», «llssssll»]
Алгоритм:
1 Поскольку нам нужно вернуть список списков, содержащий индексы, слова которых, если мы объединим их, приведут к палиндрому, имеет интуитивный смысл иметь отображение между словами в данном массиве и их соответствующими индексами. Поэтому давайте заполним хеш-карту словами и их индексами.
2 Для каждого уникального слова в массиве слов рассмотрим, что слово разделено на две подстроки, str1 и str2, причем str1 постепенно увеличивается от «» (пустой) подстроки до всего слова, в то время как str2 принимает оставшуюся часть слова. Проверьте, является ли str1 палиндромом, и если да, то есть вероятность, что он функционирует как стержень, вокруг которого может быть сформирован палиндром. Чтобы определить, действительно ли может быть сформирован палиндром, определите, существует ли на карте обратная сторона str2 и не соответствует ли она текущему индексу, участвующему в конфликте (как в случае, если str2 имеет значение «aa», и в этом случае обратная сторона str2 также является «aa» и, следовательно, может соответствовать текущему индексу на карте), чтобы функционировать как префикс для формирования палиндрома с str1 в качестве точки поворота.
3 Если перевернутая строка действительно присутствует на карте и не соответствует текущему индексу, то у вас есть одна пара палиндромов, которую можно добавить в список результатов списков. Создайте временный список и сначала добавьте индекс перевернутой строки префикса к временному списку, затем текущий индекс i и добавьте временный список к результирующему списку списков.
4 Теперь точно так же проверьте, является ли str2 палиндромом, и в этом случае он может функционировать как точка опоры, вокруг которой может быть сформирован палиндром. Убедитесь, что реверс str1 присутствует на карте и не соответствует ли текущему индексу. Также для того, чтобы рассмотреть крайний случай, когда пустая строка «» является одним из слов в массиве, необходимо выполнить итерацию до длины слова [i] включительно. Но это может привести к тому, что пустая строка «» будет рассматриваться в str2 как дубликат в дополнение к тому, что изначально рассматривается в str1. Поэтому необходимо следить за тем, чтобы str2 не равнялась пустой строке, чтобы избежать дублирования. Если все вышеперечисленные проверки выполнены, создайте временный список, добавьте индекс префикса i и индекс суффикса из карты, соответствующей обратному str1, и добавьте временный список в список результатов списков. После итерации по всему списку слов верните список результатов списков.
Тест:
1 Тест с пустыми словами в массиве слов.
2 Тест без пар палиндромов.
3 Проверьте слова, содержащие ту же букву, но увеличивающуюся длину, например [«а», «аа»]
Решение:
Анализ сложности:
Предполагая, что размер массива слов равен n, а каждое слово в худшем случае имеет длину k, затем итерация по каждому слову для формирования подстрок и реверсирование каждого слова требует затрат k, следовательно, всего k². Кроме того, поскольку мы перебираем массив слов, возникает дополнительный коэффициент n. Таким образом, общая временная сложность составляет T O (nk²). Сложность пространства равна S O (n), поскольку мы отображаем размер массива слов на хеш-карту.
