题目描述

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”]

算法

(Hash) 思路： ref

case1: 如果words数组有任何”“串，说明能和任何其他字符串组成Palindrome Pairs。
case2: 如果words数组存在中s2是s1串的reversing string，那么s1+s2 和 s2 + s1是Palindrome Pairs。
case3: 如果words数组某一子串，从0开始切割，取[0:cut], 得到s1,words数组如果还存一个s2，s2是s1[cut+1:]的reversing string，那么s2+s1是Palindrome Pairs。
case4: 和case3类似,如果words数组某一子串，从cut+1位开始切割，取s1[cut+1: len], 得到s1串，words数组还存一个s2，是s1[0: cut]的reversing string，那么s1+s2是Palindrome Pairs。
如果

Java 代码

class Solution {

    List<List<Integer>> res = new ArrayList<>();

    //build the map save the key-val pairs: String - idx
    HashMap<String, Integer> map = new HashMap<>();

    public List<List<Integer>> palindromePairs(String[] words) {
        if (words.length == 0) {
            return res;
        }

        for (int i = 0; i < words.length; i++) {
            map.put(words[i], i);
        }

        //special cases: "" can be combine with any palindrome string
        if (map.containsKey("")) {
            Integer blankIndex = map.get("");
            for (int i = 0; i < words.length; i++) {
                if (isPalindrome(words[i])) {
                    if (blankIndex == i) {
                        continue;
                    }
                    res.add(Arrays.asList(i, blankIndex));
                    res.add(Arrays.asList(blankIndex, i));
                }
            }
        }

        StringBuilder sb = null;
        //Case 2: If s2 is the reversing string of s1, then s1+s2 and s2+s1 are palindrome.
        for(int i = 0; i < words.length; i++) {
            sb = new StringBuilder(words[i]);
            String reverse = sb.reverse().toString();
            if (map.containsKey(reverse)) {
                Integer index = map.get(reverse);
                if (index == i) {
                    continue;
                }
                res.add(Arrays.asList(i, index));
            }
        }

        //Case 3: If s1[0:cut] is palindrome and there exists s2 is the reversing string of s1[cut+1:] , then s2+s1 is palindrome.
        //Case 4: Similar to case3. If s1[cut+1: ] is palindrome and there exists s2 is the reversing string of s1[0:cut] , then s1+s2 is palindrome.
        for(int i = 0; i < words.length; i++) {
            String currWord = words[i];
            for (int j = 1; j < currWord.length(); j++) {
                // Case 3
                String substring = currWord.substring(0, j);
                String reverseString = null;
                if (isPalindrome(substring)) {
                    reverseString = new StringBuilder(currWord.substring(j)).reverse().toString();
                    if (map.containsKey(reverseString)) {
                        int index = map.get(reverseString);
                        if(index == i) {
                            continue;
                        }
                        res.add(Arrays.asList(index, i));
                    }
                }

                // Case 4
                String subStr = currWord.substring(j);
                if (isPalindrome(subStr)) {
                    reverseString = new StringBuilder(currWord.substring(0, j)).reverse().toString();
                    if (map.containsKey(reverseString)) {
                        int index = map.get(reverseString);
                        if(index == i) {
                            continue;
                        }
                        res.add(Arrays.asList(i, index));
                    }
                }
            }
        }

        return res;
    }

    public boolean isPalindrome(String s) {
        if ("".equals(s)) {
            return true;
        }
        int len = s.length();
        int i = 0, j = len - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}