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] + word[j] is a palindrome.
Example 1:
Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]
Example 2:
Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> res = new ArrayList<>();
if (words == null || words.length <= 1) return res;
// Store {String: index} into map
HashMap<String, Integer> map = new HashMap<String, Integer>();
for (int i = 0; i < words.length; i++) map.put(words[i], i); // O(n)
for (int i = 0; i < words.length; i++) { // O(n)
for (int j = 0; j <= words[i].length(); j++) { // O(k) to iterate each string
// split string into two parts
String str1 = words[i].substring(0, j);
String str2 = words[i].substring(j);
// reverse(str2) + panlindromic str1 + str2 is a palindrome
if (isPanlindrome(str1)) { // O(k) to check palindrome and reverse
String str2rev = reverse(str2);
if (map.containsKey(str2rev) && map.get(str2rev) != i)
res.add(Arrays.asList(map.get(str2rev), i));
}
// str1 + panlindromic str2 + reverse(str1) is a palindrome
if (isPanlindrome(str2)) { // O(k) to check palindrome and reverse
String str1rev = reverse(str1);
if (map.containsKey(str1rev) && map.get(str1rev) != i && str2.length() != 0)
res.add(Arrays.asList(i, map.get(str1rev)));
}
}
}
return res;
}
// O(k) time to reverse the string
private String reverse(String str) {
StringBuilder sb = new StringBuilder(str);
return sb.reverse().toString();
}
// O(k) time to check whether isPanlindrome
private boolean isPanlindrome(String str) {
if (str == null || str.length() == 0) return true;
int left = 0; int right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) return false;
left++;
right--;
}
return true;
}
}
Complexity Analysis
Time Complexity: O(nk^2). 我们需要用O(n)的时间遍历所有的字符串，然后对于每个字符串（平均长度假设为k），我们需要将其拆分k次，且对每一个此拆分，我们都需要用再用O(k)的时间检查其是否为panlindrome、翻转不是panlindrome的部分。因此，总时间复杂度为O(n k^2)
Space Complexity: O(n). 我们需要使用额外的HashMap储存所有的String。如果我们考虑每次中间拆分过程中创造的String所占用空间，则复杂度为O(nk).