LeetCode: Palindrome Pairs

LeetCode: Palindrome Pairs

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”]

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
public class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
if (words == null || words.length < 2) {
return Collections.emptyList();
}

List<List<Integer>> result = new ArrayList<>();
Map<String, Integer> dict = new HashMap<>();

for (int i = 0; i < words.length; i++) {
dict.put(words[i], i);

}

for (int i = 0; i < words.length; i++) {
String a = words[i];
String reverse = getReverse(a);
if (isPalindrome(a)) {
if (dict.containsKey("") && !a.equals("")) {
result.add(getPair(i, dict.get("")));
result.add(getPair(dict.get(""), i));
}
}
if (dict.containsKey(reverse) && !reverse.equals(a)) {
result.add(getPair(i, dict.get(reverse)));
}
for (int x = 1; x < a.length(); x++) {
String right = a.substring(x);
String left = a.substring(0, x);
String rl = getReverse(left);
String rr = getReverse(right);
if (isPalindrome(right) && dict.containsKey(rl)) {
result.add(getPair(i, dict.get(rl)));
}
if (isPalindrome(left) && dict.containsKey(rr)) {
result.add(getPair(dict.get(rr), i));
}
}

}


return result;
}



private boolean isSingleCharString(String s) {
if (s == null || s.isEmpty()) {
return false;
}
char c = s.charAt(0);
for (int i = 1; i < s.length(); i++) {
if (c != s.charAt(i)) {
return false;
}
}
return true;
}

private boolean isPalindrome(String s) {
if (s == null || s.isEmpty()) {
return true;
}
int a = 0;
int b = s.length() - 1;
while (a < b) {
if (s.charAt(a) != s.charAt(b)) {
return false;
}
a++;
b--;
}
return true;
}

private String getReverse(String a) {
StringBuilder sb = new StringBuilder(a);
return sb.reverse().toString();
}

private List<Integer> getPair(int a, int b) {
List<Integer> result = new ArrayList<>();
result.add(a);
result.add(b);
return result;
}
}