336. Palindrome Pairs

Link

Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:

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

Example 2:

Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]] 
Explanation: The palindromes are ["battab","tabbat"]

Solution

針對每個word尋找其中是否有某個部分可以自己回文。ex: adaras, 其中ada已經是回文了。 此時，若能找到其他word剛好剩下沒有回文的部分(ex:ras)的revert那麼這兩個組合就可以成為一個回文:

ex: words[i]: adaras , words[j]:sar 那麼 [j, i]就可以組成一個回文: saradaras words[i]: rasada , words[j]:sar 那麼 [i, j]就可以組成一個回文: rasadasar

Time complexity O(m * n ^ 2) where m is the length of the list and the n is the length of the word.

public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> ret = new LinkedList<>();
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < words.length; i++){
            map.put(words[i], i);
        }
        
        for(int i = 0; i < words.length; i++){
            String target = words[i];
            for(int j = 0; j <= target.length(); j++){
                String preString = target.substring(0,j);
                String postString = target.substring(j);
                if(isPalindrome(preString)){
                    String revertPostString = new StringBuilder(postString).reverse().toString();
                    if(map.containsKey(revertPostString) && map.get(revertPostString) != i){
                        LinkedList<Integer> list = new LinkedList<>();
                        list.add(map.get(revertPostString));
                        list.add(i);
                        ret.add(list);
                    }
                }
                if(isPalindrome(postString)){
                    String revertPostString = new StringBuilder(preString).reverse().toString();
                    if(map.containsKey(revertPostString) && map.get(revertPostString) != i && postString.length()!=0){
                        LinkedList<Integer> list = new LinkedList<>();
                        list.add(i);
                        list.add(map.get(revertPostString));
                        ret.add(list);
                    }
                }
            }
        }
        return ret;
    }

    private boolean isPalindrome(String string) {
        int i = 0, j = string.length() - 1;
        while(j >= i){
            if(string.charAt(i) != string.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }