This is one of the finest problem till now asked to me on Trie in an interview. Fortunately was able to solve this problem, I have documented my solution in the blog.

Detailed step by step with dry run solution

https://www.yourinterviewblog.com/post/technical-question-11-palindrome-pairs