Skip to content

336. Palindrome Pairs 👍

  • Time: $O(nk^2)$, where $n = |\texttt{words}|$ and $k = |\texttt{words[i]}$
  • Space: $O(nk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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