336 Palindrome Pairs

You are given a 0-indexed array of unique strings words.

A palindrome pair is a pair of integers (i, j) such that:

• 0 <= i, j < word.length,

• i != j, and

• words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Return an array of all the palindrome pairs of words.

Example 1:

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

Example 2:

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

Example 3:

Input: words = ["a",""]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["a","a"]

Constraints:

• 1 <= words.length <= 5000

• 0 <= words[i].length <= 300

• words[i] consists of lowercase English letters.

这题呢，超级难，bruteforce呢，是T:O(n^2 * k)。

然后呢，看了答案，通过把前缀和后缀存入hashMap中优化，能优化到T:O(k^2 * n)，但n超级大的时候，会比brute force好。这里有3种情况需要加到result里：

1.存在reverse，譬如，list里有CAT和TAC。那么这对可以加

2.word1比较短，word2比较长，word2后缀是word1的reverse而且word2中间是palindrome。譬如，CAT，LOLTAC

3.word1比较长，word2比较短，word1前缀是word2的reverse而且word1中间是palindrome，譬如，CATLOL，TAC

我们每遇到一个word，就算一次prefix和suffix（剩余部分是valid palindrome），然后reverse这个prefix和suffix看是不是存在在worlist里。如果是，那么这两个可以组成一对。

还有一种解法是用Trie，因为我们这里算了一堆prefix，suffix。具体做法要看solution，但其实时间复杂度没变。听说是如果我们要support变增加，变查找的功能时候，Trie比较好。

// 抄了一遍
public List<List<Integer>> palindromePairs(String[] words) {
    if (words == null || words.length == 0) {
        return null;
    }

    Map<String, Integer> wordMap = new HashMap<>();
    int len = words.length;
    for (int i = 0; i < len; i++) {
        wordMap.put(words[i], i);
    }

    List<List<Integer>> result = new ArrayList<>();
    for (String word : wordMap.keySet()) {
        int curInd = wordMap.get(word);
        String reverseWord = new StringBuilder(word).reverse().toString();

        // case 1, reverse of this word exist
        if (wordMap.containsKey(reverseWord) && wordMap.get(reverseWord) != curInd) {
            result.add(Arrays.asList(curInd, wordMap.get(reverseWord)));
        }

        // case 2, suffix, current word is 2nd word
        for (String suffix : getAllValidSuffix(word)) {
            String reverseSuffix = new StringBuilder(suffix).reverse().toString();
            if (wordMap.containsKey(reverseSuffix)) {
                result.add(Arrays.asList(wordMap.get(reverseSuffix), curInd));
            }
        }

        // case 3, prefix, current word is 1st word
        for (String prefix : getAllValidPrefix(word)) {
            String reversePrefix = new StringBuilder(prefix).reverse().toString();
            if (wordMap.containsKey(reversePrefix)) {
                result.add(Arrays.asList(curInd, wordMap.get(reversePrefix)));
            }
        }
    }

    return result;
}

private List<String> getAllValidSuffix(String word) {
    List<String> suffixes = new ArrayList<>();
    for (int i = 0; i < word.length(); i++) {
        // 前面是valid palindrome
        if (isPalindrome(word, 0, i)) {
            // 把后半部分放入suffix list里
            suffixes.add(word.substring(i + 1, word.length()));//houmia
        }
    }
    return suffixes;
}

private List<String> getAllValidPrefix(String word) {
    List<String> prefixes = new ArrayList<>();
    for (int i = 0; i < word.length(); i++) {
        // 后面是valid palindrome
        if (isPalindrome(word, i, word.length() - 1)) {
            // 把前半部分放入prefix list里
            prefixes.add(word.substring(0, i));
        }
    }
    return prefixes;
}

private boolean isPalindrome(String str, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
        if (str.charAt(i) != str.charAt(j)) {
            return false;
        }
    }
    return true;
}


// 暴力算法
public List<List<Integer>> palindromePairs(String[] words) {
    if (words == null || words.length == 0) {
        return null;
    }

    List<List<Integer>> result = new ArrayList<>();
    int len = words.length;
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            if (i == j) {
                continue;
            }

            String combinedStr = words[i] + words[j];
            if (isPalindrome(combinedStr)) {
                List<Integer> oneAns = Arrays.asList(i, j);
                result.add(oneAns);
            }
        }
    }
    return result;
}

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