Palindrome Pairs
给一个字符串数组, 返回通过链接其中的两个字符串, 能组成的回文的pairs. 这个就是dfs加剪枝
public class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> ret = new ArrayList<>();
if (words == null || words.length < 2) return ret;
Map<String, Integer> map = new HashMap<>();
for (int i=0; i<words.length; i++) {
map.put(words[i], i);
}
for (int i=0; i<words.length; i++) {
for (int j=0; j<=words[i].length(); j++) { // notice it should be "j <= words[i].length()"
String str1 = words[i].substring(0, j);
String str2 = words[i].substring(j);
if (isPalindrome(str1)) {
String str2rvs = new StringBuilder(str2).reverse().toString();
if (map.getOrDefault(str2rvs, i) != i) {
ret.add(Arrays.asList(map.get(str2rvs), i));
}
}
if (isPalindrome(str2) && str2.length() != 0) {
String str1rvs = new StringBuilder(str1).reverse().toString();
// check "str.length() != 0" to avoid duplicates
if (map.getOrDefault(str1rvs, i) != i) {
ret.add(Arrays.asList(i, map.get(str1rvs)));
}
}
}
}
return ret;
}
private boolean isPalindrome(String str) {
for (int l = 0, r = str.length() - 1; l <= r; l ++, r --) {
if (str.charAt(l) != str.charAt(r)) {
return false;
}
}
return true;
}
}