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”]
public class Solution { public List<List<Integer>> palindromePairs(String[] words) { List<List<Integer>> res = new ArrayList<List<Integer>>(); HashMap<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++) { for (int j = 0; j <= words[i].length(); j++) { String str1 = words[i].substring(0, j); String str2 = words[i].substring(j); if(ispld(str1)) { String sb = new StringBuilder(str2).reverse().toString(); if(map.containsKey(sb) && map.get(sb) != i) { List<Integer> tmp = new ArrayList<>(); tmp.add(map.get(sb)); tmp.add(i); res.add(tmp); } } if(ispld(str2)) { String sb = new StringBuilder(str1).reverse().toString(); if(map.containsKey(sb) && map.get(sb) != i && str2.length() != 0) { List<Integer> tmp = new ArrayList<>(); tmp.add(i); tmp.add(map.get(sb)); res.add(tmp); } } } } return res; } public boolean ispld(String str){ int left = 0; int right = str.length() - 1; while (left < right) { if(str.charAt(left++) != str.charAt(right--)) return false; } return true; }}新闻热点
疑难解答
