336. Palindrome Pairs LeetCode Solution

Last updated: February 17, 2025

In this guide, you will get 336. Palindrome Pairs LeetCode Solution with the best time and space complexity. The solution to Palindrome Pairs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Palindrome Pairs solution in C++
Palindrome Pairs solution in Java
Palindrome Pairs solution in Python
Additional Resources

336. Palindrome Pairs LeetCode Solution image

Problem Statement of Palindrome Pairs

You are given a 0-indexed array of unique strings words.
A palindrome pair is a pair of integers (i, j) such that:

0 <= i, j < words.length,
i != j, and
words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Return an array of all the palindrome pairs of words.
You must write an algorithm with O(sum of words[i].length) runtime complexity.

Example 1:

Input: words = [“abcd”,”dcba”,”lls”,”s”,”sssll”]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are [“abcddcba”,”dcbaabcd”,”slls”,”llssssll”]

Example 2:

Input: words = [“bat”,”tab”,”cat”]
Output: [[0,1],[1,0]]
Explanation: The palindromes are [“battab”,”tabbat”]

Example 3:

Input: words = [“a”,””]
Output: [[0,1],[1,0]]
Explanation: The palindromes are [“a”,”a”]

Constraints:

1 <= words.length <= 5000
0 <= words[i].length <= 300
words[i] consists of lowercase English letters.

Complexity Analysis

Time Complexity: O(nk^2), where n = |\texttt{words}| and k = |\texttt{words[i]}
Space Complexity: O(nk)

336. Palindrome Pairs LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> palindromePairs(vector<string>& words) {
    vector<vector<int>> ans;
    unordered_map<string, int> map;  // {reversed word: its index}

    for (int i = 0; i < words.size(); ++i) {
      string word = words[i];
      ranges::reverse(word);
      map[word] = i;
    }

    for (int i = 0; i < words.size(); ++i) {
      const string& word = words[i];
      // a special case to prevent duplicate calculation
      if (const auto it = map.find("");
          it != map.cend() && it->second != i && isPalindrome(word))
        ans.push_back({i, it->second});
      for (int j = 1; j <= word.length(); ++j) {
        const string& l = word.substr(0, j);
        const string& r = word.substr(j);
        if (const auto it = map.find(l);
            it != map.cend() && it->second != i && isPalindrome(r))
          ans.push_back({i, it->second});
        if (const auto it = map.find(r);
            it != map.cend() && it->second != i && isPalindrome(l))
          ans.push_back({it->second, i});
      }
    }

    return ans;
  }

 private:
  bool isPalindrome(const string& word) {
    int l = 0;
    int r = word.length() - 1;
    while (l < r)
      if (word[l++] != word[r--])
        return false;
    return true;
  }
};
/* code provided by PROGIEZ */

336. Palindrome Pairs LeetCode Solution in Java

class Solution {
  public List<List<Integer>> palindromePairs(String[] words) {
    List<List<Integer>> ans = new ArrayList<>();
    Map<String, Integer> map = new HashMap<>(); // {reversed word: its index}

    for (int i = 0; i < words.length; ++i)
      map.put(new StringBuilder(words[i]).reverse().toString(), i);

    for (int i = 0; i < words.length; ++i) {
      final String word = words[i];
      // a special case to prevent duplicate calculation
      if (map.containsKey("") && map.get("") != i && isPalindrome(word))
        ans.add(Arrays.asList(i, map.get("")));
      for (int j = 1; j <= word.length(); ++j) {
        final String l = word.substring(0, j);
        final String r = word.substring(j);
        if (map.containsKey(l) && map.get(l) != i && isPalindrome(r))
          ans.add(Arrays.asList(i, map.get(l)));
        if (map.containsKey(r) && map.get(r) != i && isPalindrome(l))
          ans.add(Arrays.asList(map.get(r), i));
      }
    }

    return ans;
  }

  private boolean isPalindrome(final String word) {
    int l = 0;
    int r = word.length() - 1;
    while (l < r)
      if (word.charAt(l++) != word.charAt(r--))
        return false;
    return true;
  }
}
// code provided by PROGIEZ

336. Palindrome Pairs LeetCode Solution in Python

class Solution:
  def palindromePairs(self, words: list[str]) -> list[list[int]]:
    ans = []
    dict = {word[::-1]: i for i, word in enumerate(words)}

    for i, word in enumerate(words):
      if "" in dict and dict[""] != i and word == word[::-1]:
        ans.append([i, dict[""]])

      for j in range(1, len(word) + 1):
        l = word[:j]
        r = word[j:]
        if l in dict and dict[l] != i and r == r[::-1]:
          ans.append([i, dict[l]])
        if r in dict and dict[r] != i and l == l[::-1]:
          ans.append([dict[r], i])

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents