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 PalindromePairs {
public boolean isPalindrome(String string) {
char c[]=string.toCharArray();
boolean flag=true;
for (int i = 0; i < c.length/2; i++) {
if (c[i]!=c[c.length-i-1]) {
flag=false;
break;
}
}
return flag;
}
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> b= new ArrayList<List<Integer>>();
for (int i = 0; i < words.length; i++) {
for (int j = 0; j < words.length; j++) {
if (i!=j) {
String string=words[i]+words[j];
if (isPalindrome(string)) {
List<Integer> a= new ArrayList<Integer>();
a.add(i);
a.add(j);
b.add(a);
}
}
}
}
return b;
}
public static void main(String[] args) {
String [] words={"hijajcd","hjhgahbcegj"};
PalindromePairs pairs=new PalindromePairs();
System.out.println(pairs.palindromePairs(words));
}
}
方法二：
利用
public class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> resultList= new ArrayList<List<Integer>>();
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++) {
for (int j = 0; j <= words[i].length(); j++) {
String subString=words[i].substring(0,j);
String subString2=words[i].substring(j);
if (isPalindrome(subString)) {
if (map.get(reverseString(subString2))!=null) {
ArrayList<Integer> arrayList=new ArrayList<Integer>(2);
arrayList.add(map.get(reverseString(subString2)));
arrayList.add(map.get(words[i]));
if (!arrayList.get(0).equals(arrayList.get(1))) {
resultList.add(arrayList);
}
}
}
if (isPalindrome(subString2)) {
if (map.get(reverseString(subString))!=null) {
ArrayList<Integer> arrayList=new ArrayList<Integer>(2);
arrayList.add(map.get(words[i]));
arrayList.add(map.get(reverseString(subString)));
if (!arrayList.get(0).equals(arrayList.get(1))) {
resultList.add(arrayList);
}
}
}
}
}
HashSet hashSet=new HashSet(resultList);
resultList.clear();
resultList.addAll(hashSet);
return resultList;
}
public boolean isPalindrome(String string) {
char c[]=string.toCharArray();
boolean flag=true;
for (int i = 0; i < c.length/2; i++) {
if (c[i]!=c[c.length-i-1]) {
flag=false;
break;
}
}
return flag;
}
public String reverseString(String string) {
char[] chars=string.toCharArray();
char[] result=new char[chars.length];
for (int i = 0; i < chars.length; i++) {
result[chars.length-i-1]=chars[i];
}
return new String(result);
}
}