Палиндром Пары

Question

Учитывая список уникальных слов, найдите все пары различных индексов (i, j) в данном списке, чтобы конкатенация двух слов, то есть слов [i] + words [j], была палиндромом.

Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]


How can I solve this using Trie data structure?

Answer 1

С помощью грубой силы вы можете легко найти все палиндромы в O (N ² K) , где N - количество слов в списке и K - это максимальная длина, проверяемая на палиндром.

Используя Trie You, вы можете достичь своих результатов в O (NK ² ) .

псевдокод

1) Create an empty Trie.
2) Do following for every word:-
    a) Insert reverse of current word.
    b) Also store up to which index it is 
       a palindrome.
3) Traverse list of words again and do following 
   for every word.
    a) If it is available in Trie then return true
    b) If it is partially available
         Check the remaining word is palindrome or not 
         If yes then return true that means a pair
         forms a palindrome.
         Note: Position upto which the word is palindrome
               is stored because of these type of cases.

Ссылка : Палиндром Пары