Palindrome Pairs

这题第一个解法是 O(n ^ 2 * k)的时间复杂度, n是array.length, k是average word's length in the array

伪代码
for 0 - i
    for i + 1 - word.length
        word1 = words[i], word2 = words[j]
        if (isPalindrome(word1 + word2)) 
            add (word1 + word2) to result
        if (isPalindrome(word2 + word1)) 
            add (word2 + word1) to result

两重for循环的复杂度是O(n ^ 2)， isPalindrome(word)是O(k)

第二种解，可以把复杂度优化到O(n * k ^ 2)，用了O(n)的空间。

这里有个edge case在内层的for循环里，j <= words.length()，带等号。如果没有等号，["a", ""]只有一个结果了。

而加了等号以后，在检查if (isPaindrome(str2))后再检查一下str2是否equals""，防止在result有重复的结果。

public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (words == null || words.length == 0) {
            return result;
        }

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

        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            for (int j = 0; j <= word.length(); j++) {
                String str1 = word.substring(0, j);
                String str2 = word.substring(j);

                if (isPalindrome(str1)) {
                    String newWord = new StringBuilder(str2).reverse().toString();
                    if (map.containsKey(newWord) && map.get(newWord) != i) {
                        result.add(Arrays.asList(map.get(newWord), i));
                    }
                }
                if (isPalindrome(str2) && str2.length() != 0) {
                    String newWord = new StringBuilder(str1).reverse().toString();
                    if (map.containsKey(newWord) && map.get(newWord) != i) {
                        result.add(Arrays.asList(i, map.get(newWord)));
                    }
                }
            }
        }
        return result;
    }

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