题目
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.
答案
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> list = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();
Set<List<Integer>> dup = new HashSet<>();
for(int i = 0; i < words.length; i++) {
StringBuilder sb = new StringBuilder(words[i]);
String reversed = sb.reverse().toString();
map.put(reversed, i);
}
for(int i = 0; i < words.length; i++) {
for(int j = 0; j < words[i].length() + 1; j++) {
String left = words[i].substring(0, j);
String right = words[i].substring(j);
Integer left_idx = map.get(left);
if(left_idx != null && left_idx != i && is_pal(right)) {
List<Integer> l = Arrays.asList(new Integer[]{i, left_idx});
if(!dup.contains(l)) {
dup.add(l);
list.add(l);
}
}
Integer right_idx = map.get(right);
if(right_idx != null && right_idx != i && is_pal(left)) {
List<Integer> l = Arrays.asList(new Integer[]{right_idx, i});
if(!dup.contains(l)) {
dup.add(l);
list.add(l);
}
}
}
}
return list;
}
public boolean is_pal(String s) {
int l = 0, r = s.length() - 1;
while(l < r) {
if(s.charAt(l++) != s.charAt(r--)) return false;
}
return true;
}
}
网友评论