336. Palindrome Pairs

Version #2 Trie[TODO]


Version #1 HashMap of reversed word

1. abcd v.s. dcba
if we cut abcd by either ("", "abcd") or ("abce", "") we'll find a mapped "abcd(reversed dcba)" in hash map -> we add 2 result (0, 1) & (1, 0)
And when dcba comes, we also add (1, 0) and (0, 1)
In case of this kind of duplicate, I wanted to stop cutting when left | right -> right.length() at least 1
So we'll only have ""|"abcd" for (1, 0) and ""|"dcba" for (0, 1)
However we have edge case 2 ->
2. "a" ,""
When "a" came, we have ""|"a" and have matched "" in map
When "" came, we only allow k < word.length() so "" will never be cutted
That's a bug

This answer handles this in a very smart way-> we still try to cut from 0 to left.lengh()
if right.length() == 0, we don't add
So it satisfies the 1st edge case
For the 2nd edge case -> we still have "a"|"" which is (0, 1) for "a", ""|"a" (1, 0) for "a"
Now when "" came, we have ""|"" it will never be added
Time O(N k^2) k is the average length of words

17.46 %
class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> result = new ArrayList<>();
if (words == null) {
return result;
}
// key -> reversed word, value -> index of the original word
Map<String, Integer> reversedWords = new HashMap<>();
for (int i = 0; i < words.length; i++) {
reversedWords.put(new StringBuilder(words[i]).reverse().toString(), i);
}

for (int i = 0; i < words.length; i++) {
String word = words[i];
// partition word into left | right
// left | right | candidate or  candidate | left | right
for (int k = 0; k <= word.length(); k++) {
String left = word.substring(0, k);
String right = word.substring(k, word.length());
int j;
if (reversedWords.containsKey(left) && (j = reversedWords.get(left)) != i && isPalindrome(right)) {
result.add(Arrays.asList(i, j));
}
if (reversedWords.containsKey(right) && left.length() != 0 && (j = reversedWords.get(right)) != i && isPalindrome(left)) {
result.add(Arrays.asList(reversedWords.get(right), i));
}
}
}
return result;
}
private boolean isPalindrome(String word) {
int len = word.length();
int i = 0;
while (i < len / 2) {
if (word.charAt(i) != word.charAt(len - i - 1)) {
return false;
}
i++;
}
return true;
}
}