05 August 2008
Given a list of unique words, find all pairs of distinct indices 1
(i, j)
1
words[i] + words[j]
Example 1:
1
2
3
Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]
Example 2:
1
2
3
Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]
给了一个字符串数组，要求找到所有能组合成回文的两个词；暴力解法过不了；用了字典树Trie的结构，参考这里，暴力解法就是找出所有pairs，逐一验证isPalindrome. 时间复杂度O(N^2*k)。
palindrome最大的特性就是对称，按长度的奇偶可以分为str，char，reverse(str)和str，reverse(str)型。 我们有一个str，在i这个位置进行切分，得到的前半部分是一个palindrome。比如”lls”, 变成”ll”， “s”。 已知”ll”是palindrome，我们只需要知道reverse(”s”) 放到前边就可以了。 reverse(”s”)“ll””s”, 即reverse(str) PalindromeSubString str的类型。
还有一种就是后半部分是palindrome, 我们找到前半部分的reverse,拼到后面。[“abcdc”, “ba”]。 “cdc”是palindrome, reverse(ab) 就是 “ba”, 我们有这样的string出现过。
代码细节就是有一个isPalindrome的helper function。 一个hashmap存入所有 paris加速查询。 容易出bug的两个地方, 以[“abcd”, “dcba”, “lls”, “s”, “sssll”]为例。 1. 如果一个str本身就是panlindrome，reverse就是本身，一定在hashmap里，去重的方法就是判断map.get(reverse(str)) != i. [[1,0],[0,1],[3,2],[3,3],[2,4]] 2. 我们在切割str的时候，j ==0时str变成”“和”str”, j == str.length()的时候str变成”str”和”“。 “abcd”, “dcba”这两个互为reverse的string, 在”abcd”尾部加上”dcba”也就是在”dcba”头部加上”abcd”. 所以后部分不能为空，否则就和头部为空的情况重复了。 [[1,0],[0,1],[0,1],[1,0],[3,2],[2,4]]
空间复杂度因为用了额外的hashmap来储存，需要O(N)空间。 时间复杂度每个str分为两个部分，调用isPalindrome,前后两部分总长度为k. 所以每次调用为O(k)一共(k+1)次。 然后一共有N个str, 总共时间复杂度为O(N*k^2).
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> result = new ArrayList<>();
if (words == null || words.length == 0) {
return result;
}
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < words.length; i++) {//将单词和对应的索引在map中映射
map.put(words[i], i);
}
for (int i = 0; i < words.length; i++) {//遍历所有单词
for (int j = 0; j <= words[i].length(); j++) {
//切割每个单词成两部分，只要其中一部分是回文串，而且另一部分翻转后能够在map中找到，说明就可以组成回文对
String str1 = words[i].substring(0, j);//单词left
String str2 = words[i].substring(j);//单词right
if (isPalindrome(str1)) {
String str2rvs = new StringBuilder(str2).reverse().toString();//翻转单词，准备下一步查map
if (map.containsKey(str2rvs) && map.get(str2rvs) != i) {//包含翻转后的单词并且不是单词本身
List<Integer> list = new ArrayList<>();
list.add(map.get(str2rvs));
list.add(i);
result.add(list);
}
}
//同上
if (isPalindrome(str2) && str2.length() != 0) {
String str1rvs = new StringBuilder(str1).reverse().toString();
if(map.containsKey(str1rvs) && map.get(str1rvs) != i) {
List<Integer> list = new ArrayList<>();
list.add(i);
list.add(map.get(str1rvs));
result.add(list);
}
}
}
}
return result;
}
//判断字符串是否是回文
private boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}