题目:
题解:
// 哈希表实现
class Solution {public List<List<Integer>> palindromePairs(String[] words) {List<List<Integer>> res = new ArrayList<>();int n = words.length;Map<String, Integer> indices = new HashMap<>();for (int i = 0; i < n; ++i) {String w = new StringBuilder(words[i]).reverse().toString();indices.put(w, i);}for (int i = 0; i < n; ++i) {int m = words[i].length();if (m == 0) {continue;}for (int j = 0; j <= m; ++j) {if (isPalindrome(words[i], j, m - 1)) {String w = words[i].substring(0, j);int leftId = indices.getOrDefault(w, -1);if (leftId != -1 && leftId != i) {res.add(Arrays.asList(i, leftId));}}if (j != 0 && isPalindrome(words[i], 0, j - 1)) {String w = words[i].substring(j, m);int rightId = indices.getOrDefault(w, -1);if (rightId != -1 && rightId != i) {res.add(Arrays.asList(rightId, i));}}}}return res;}public boolean isPalindrome(String s, int left, int right) {int n = right - left + 1;for (int i = 0; i < n / 2; ++i) {if (s.charAt(left + i) != s.charAt(right - i)) {return false;}}return true;}
}