Description
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
Example 1:1
2
3Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]
Example 2:1
2
3Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]
Solution
$O(K*N^2)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
HashMap<String, Integer> map = new HashMap<>();
List<List<Integer>> res = new ArrayList<>();
if (words == null || words.length < 2) return res;
for (int i = 0; i < words.length; i++) map.put(words[i], i);
if (map.containsKey("")){
for (String word: map.keySet()){
if (isPalindrome(word) && !word.equals("")){
res.add(Arrays.asList(map.get(""), map.get(word)));
res.add(Arrays.asList(map.get(word), map.get("")));
}
}
}
for (String word: map.keySet()){
String rev = new StringBuffer(word).reverse().toString();
if (map.containsKey(rev) && map.get(rev)!=map.get(word))
res.add(Arrays.asList(map.get(word), map.get(rev)));
}
for (String word: words){
for (int i = 1; i < word.length(); i++){
String p1 = word.substring(0, i);
String p2 = word.substring(i);
if (isPalindrome(p1)){
String rev = new StringBuffer(p2).reverse().toString();
if (map.containsKey(rev) && map.get(rev)!=map.get(word)){
res.add(Arrays.asList(map.get(rev), map.get(word)));
}
}
if (isPalindrome(p2)){
String rev = new StringBuffer(p1).reverse().toString();
if (map.containsKey(rev) && map.get(rev) != map.get(word)){
res.add(Arrays.asList(map.get(word), map.get(rev)));
}
}
}
}
return res;
}
private boolean isPalindrome(String s){
String rev= new StringBuffer(s).reverse().toString();
if (s.equals(rev)) return true;
else return false;
}
}