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];
      reverse(begin(word), end(word));
      map[word] = i;
    }

    for (int i = 0; i < words.size(); ++i) {
      const string& word = words[i];
      // special case to prevent duplicate calculation
      if (map.count("") && map[""] != i && isPalindrome(word))
        ans.push_back({i, map[""]});
      for (int j = 1; j <= word.length(); ++j) {
        const string& l = word.substr(0, j);
        const string& r = word.substr(j);
        if (map.count(l) && map[l] != i && isPalindrome(r))
          ans.push_back({i, map[l]});
        if (map.count(r) && map[r] != i && isPalindrome(l))
          ans.push_back({map[r], 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;
  }
};

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];
      // 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;
  }
}

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