Leetcode Palindrome Pairs problem solution

In this Leetcode Palindrome Pairs problem solution we have given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words [i] + words[j] is a palindrome.

Problem solution in Python.

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        rmap={w[::-1]:i for i,w in enumerate(words)}
        res=[]
        for i,wrd in enumerate(words):
            rev=wrd[::-1]
            if wrd in rmap:                        
                if rmap[wrd]!=i:                   
                    res.append((i,rmap[wrd]))
            for j in range(1,len(wrd)+1):
                if wrd[:-j] in rmap and wrd[-j:]==rev[:j]:
                    res.append((i,rmap[wrd[:-j]]))
                if wrd[j:] in rmap and wrd[:j]==rev[-j:]:
                    res.append((rmap[wrd[j:]],i))
        return res

Problem solution in Java.

class Solution {
    class TrieNode{
        TrieNode[] children=new TrieNode[26];
        int wordIndex=-1;
        List<Integer> restIsPalindrome;
        TrieNode(){
            restIsPalindrome=new ArrayList<>();
        }
    }
    TrieNode root=new TrieNode();
    int n;
    List<List<Integer>> res=new ArrayList<>();
    
    public List<List<Integer>> palindromePairs(String[] words) {
        n=words.length;
        
        for(int i=0;i<n;i++){
            add(words[i], i);
        }
        
        for(int i=0;i<n;i++){
            search(words[i], i);
        }
        
        return res;
    }
    private void search(String word, int wordIndex){
        TrieNode cur=root;
        char[] chs=word.toCharArray();
        for(int i=0;i<chs.length;i++){
            int j=chs[i]-'a';
            if(cur.wordIndex != -1 && isPalindrome(chs, i, chs.length-1)){
                res.add(Arrays.asList(wordIndex, cur.wordIndex));
            }
            
            if(cur.children[j] == null){
                return;
            }
            
            cur=cur.children[j];
        }
        if(cur.wordIndex != -1 && cur.wordIndex != wordIndex){
            res.add(Arrays.asList(wordIndex, cur.wordIndex));
        }
        
        for(int j:cur.restIsPalindrome){
            res.add(Arrays.asList(wordIndex, j));
        }
    }
    private void add(String word, int wordIndex){
        TrieNode cur=root;
        char[] chs=word.toCharArray();
        for(int i=chs.length-1;i>=0;i--){
            int j=chs[i]-'a';
            if(isPalindrome(chs, 0, i)){
                cur.restIsPalindrome.add(wordIndex);
            }
            if(cur.children[j] == null){
                cur.children[j]=new TrieNode();
            }
            
            cur=cur.children[j];
        }
        
        cur.wordIndex=wordIndex;
    }
    
    private boolean isPalindrome(char[] chs, int i, int j){
        while(i < j){
            if(chs[i++] != chs[j--]){
                return false;
            }
        }   
            return true;
    }
    
}

Problem solution in C++.

class Solution {
public:
    bool palindrome(string s){
        int i=0,j=s.size()-1;
        while(i<j){
            if(s[i++]!=s[j--])  return false;
        }
        return true;
    }
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> ans;
        if(words.size()<=1) return ans;
        unordered_map<string,int> m;
        for(int i=0;i<words.size();i++){
            string rev = string(words[i].rbegin(),words[i].rend());
            m[rev] = i+1; 
        } 
        for(int i=0;i<words.size();i++){
            if(m[words[i]] && i+1!=m[words[i]])  ans.push_back({i,m[words[i]]-1});
            
            for(int j=words[i].size()-1;j>=0;j--){
                if(palindrome(words[i].substr(j))){
                    if(m[words[i].substr(0,j)]){
                        ans.push_back({i,m[words[i].substr(0,j)]-1});
                    }
                }
            }
            for(int j=0;j<words[i].size();j++){
                if(palindrome(words[i].substr(0,j+1))){
                    if(m[words[i].substr(j+1)]){
                        ans.push_back({m[words[i].substr(j+1)]-1,i});
                    }
                }
            }
        } 
        return ans;
    }
};