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”]
思路： palindrome最大的特性就是对称，按长度的奇偶可以分为str,char,reverse(str)还有 str,reverse(str)型。 我们有一个str,在i这个位置进行切分，得到的前半部分是一个palindrome. 比如”lls”, 变成”ll”, “s”. 已知”ll”是palindrome，我们只需要知道reverse(“s”) 放到前边就可以了。 reverse(“s”)”ll”“s”, 即reverse(str) PalindromeSubString str的类型。
还有一种就是后半部分是palindrome, 我们找到前半部分的reverse,拼到后面。[“abcdc”, “ba”]。 “cdc”是palindrome, reverse(ab) 就是 “ba”, 我们有这样的string出现过。
代码细节就是有一个isPalindrome的helper function。 一个hashmap存入所有
class Solution { public List<List<Integer>> palindromePairs(String[] words) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if(words == null || words.length == 0) return res; 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++){ 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 str2rvs = new StringBuilder(str2).reverse().toString(); if(map.containsKey(str2rvs) && map.get(str2rvs) != i){ List<Integer> list = new ArrayList<Integer>(); list.add(map.get(str2rvs)); list.add(i); res.add(list); } } if(isPalindrome(str2) && str2.length() != 0){ String str1rvs = new StringBuilder(str1).reverse().toString(); if(map.containsKey(str1rvs) && map.get(str1rvs) != i){ List<Integer> list = new ArrayList<Integer>(); list.add(i); list.add(map.get(str1rvs)); res.add(list); } } } } return res; } public boolean isPalindrome(String s){ int left = 0, right = s.length() - 1; while(left < right){ if(s.charAt(left++) != s.charAt(right--)) return false; } return true; } }