Palindrome Pairs
给一个字符串数组, 返回通过链接其中的两个字符串, 能组成的回文的pairs. 这个就是dfs加剪枝
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
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; } } |