- 对每个word,如果它翻转过来之后[:n]或者[n:]和map中已有的key相同,且剩下的一部分是palindrome,那么它们能组成palindrome
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> pairs = new LinkedList<>();
if (words == null) return pairs;
HashMap<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) {
int l = 0, r = 0;
while (l <= r) {
String s = words[i].substring(l, r);
Integer j = map.get(new StringBuilder(s).reverse().toString());
if (j != null && i != j && isPalindrome(words[i].substring(l == 0 ? r : 0, l == 0 ? words[i].length() : l)))
pairs.add(Arrays.asList(l == 0 ? new Integer[]{i, j} : new Integer[]{j, i}));
if (r < words[i].length()) ++r;
else ++l;
}
}
return pairs;
}
private boolean isPalindrome(String s) {
for (int i = 0; i < s.length()/2; ++ i)
if (s.charAt(i) != s.charAt(s.length()-1-i))
return false;
return true;
}
}
- 用trie实现,就不用两次遍历这个word判断是否存在在map中
网友评论