Given a list of unique words, find all pairs [i,j] such that words[i]+words[j] is a palindrome.
Input: ["abcd","dcba","lls","s","sssll"] → Output: [[0,1],[1,0],[3,2],[2,4]]Input: ["bat","tab","cat"] → Output: [[0,1],[1,0]]
Use a HashMap. For each word, check its prefixes and suffixes: if prefix is palindrome, reversed suffix is a match; if suffix is palindrome, reversed prefix is a match.
- Build Map: word -> index.
- For each word w and each split (prefix, suffix):
- If prefix is palindrome and reversed(suffix) in map: add pair.
- If suffix is palindrome and reversed(prefix) in map: add pair.
- Handle empty string case.
import java.util.*;
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
Map<String,Integer> map = new HashMap<>();
for (int i = 0; i < words.length; i++) map.put(words[i], i);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
String w = words[i];
for (int j = 0; j <= w.length(); j++) {
String p = w.substring(0, j), s = w.substring(j);
if (isPalin(p)) {
String rev = new StringBuilder(s).reverse().toString();
if (map.containsKey(rev) && map.get(rev) != i)
res.add(Arrays.asList(map.get(rev), i));
}
if (s.length() > 0 && isPalin(s)) {
String rev = new StringBuilder(p).reverse().toString();
if (map.containsKey(rev) && map.get(rev) != i)
res.add(Arrays.asList(i, map.get(rev)));
}
}
}
return res;
}
private boolean isPalin(String s) {
int l=0,r=s.length()-1;
while(l<r) if(s.charAt(l++)!=s.charAt(r--)) return false;
return true;
}
}
- Time Complexity: O(N * L^2)
- Space Complexity: O(N * L)