【leetcode】String——Palindrome Pairs（336）

题目：

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: Given words = ["bat", "tab", "cat"] Return [[0, 1], [1, 0]] The palindromes are ["battab", "tabbat"] Example 2: Given words = ["abcd", "dcba", "lls", "s", "sssll"] Return [[0, 1], [1, 0], [3, 2], [2, 4]] The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]

错误思路：words里面所有的String组合，判断两两连接后的String是否回文。TLE！

正确思路：针对每个String，单独分析。

String 截取两半 |-----str1------|-----str2-----|  

如果str1是回文，那么 把str2翻转，放在左边，新的String也是回文，只要判断翻转后的str2是否在words里即可。 |-----2rts------|------str1-----|-----str2-----|

如果str2是回文，那么 把str1翻转，放在右边，新的String也是回文，只要判断翻转后的str1是否在words里即可。|------str1-----|-----str2-----|------1rts------|

但是此过程会出现重复。举例，如果 words里面有abc 和 cba ，分析abc的时候，可能会得到把cba放在abc的左边；分析cba的时候可能会得到把abc放在右边。

所以要过滤重复的。可以在第二个判断中，也就是如果str2是回文的情况下，如果str2为空，长度为0，则不添加结果。

因为str2为空时，新String为|------str1-----|------1rts------|，这个会和 分析[翻转后的str1]时，第一个判断中str1为空重复。

代码：

public List<List<Integer>> palindromePairs(String[] words) { List<List<Integer>> results = new ArrayList<>(); Map<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++){ for(int j=0;j<=words[i].length();j++){ String str1 = words[i].substring(0, j); String str2 = words[i].substring(j); if(isPalindrome(str1)){ String needAddToLeft = new StringBuffer(str2).reverse().toString(); if(map.containsKey(needAddToLeft)&&map.get(needAddToLeft)!=i){ results.add(new ArrayList<>(Arrays.asList(map.get(needAddToLeft),i))); } } if(isPalindrome(str2)){ String needAddToRight = new StringBuffer(str1).reverse().toString(); if(map.containsKey(needAddToRight)&&map.get(needAddToRight)!=i&&str2.length()!=0){ results.add(new ArrayList<>(Arrays.asList(i,map.get(needAddToRight)))); } } } } return results; } private boolean isPalindrome(String s){ if(s.equals("")) return true; int start =0; int end = s.length()-1; while(start<=end){ if(s.charAt(start)!=s.charAt(end)) return false; else{ start++; end--; } } return true; }