// 5.20
// 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 List<List<Integer>> palindromePairs(String[] words) { //Time Limit Exceeded
List<List<Integer>> list = new ArrayList<List<Integer>>();
for (int i = 0; i < words.length; i++) {
for (int j = 0; j < words.length; j++) {
if (i != j && twoWordIntegrateIsPalindrome(words[i],words[j])) {
List<Integer> tempList = new ArrayList<Integer>(Arrays.asList(i,j));
list.add(tempList);
}
}
}
return list;
}
static boolean twoWordIntegrateIsPalindrome(String str1, String str2) {
StringBuffer str = new StringBuffer(str1 + str2);
return (str1 + str2).equals(str.reverse().toString());
}
AC版
public List<List<Integer>> palindromePairs1(String[] words) { //Time Limit Exceeded
List<List<Integer>> list = 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 preString = words[i].substring(0,j);
String laString = words[i].substring(j);
if (isPalindrome(preString)) {
String tempString = new StringBuffer(laString).reverse().toString();
if (map.containsKey(tempString) && map.get(tempString) != i) {
List<Integer> tempList = new ArrayList<Integer>(Arrays.asList(map.get(tempString),i));
list.add(tempList);
}
}
if (isPalindrome(laString)) {
String tempString = new StringBuffer(preString).reverse().toString();
if (map.containsKey(tempString) && map.get(tempString) != i && laString.length() != 0) {
List<Integer> tempList = new ArrayList<Integer>(Arrays.asList(i,map.get(tempString)));
list.add(tempList);
}
}
}
}
return list;
}
static boolean isPalindrome(String str) {
String str1 = new StringBuffer(str).reverse().toString();
return str1.equals(str);
}
网友评论