Keshawn_lu's Blog

Leetcode 336. 回文对

字数统计: 816阅读时长: 3 min
2020/08/06 Share

题目简介:

给定一组 互不相同 的单词, 找出所有不同 的索引对(i, j),使得列表中的两个单词, words[i] + words[j] ,可拼接成回文串。

示例 1:

1
2
3
输入:["abcd","dcba","lls","s","sssll"]
输出:[[0,1],[1,0],[3,2],[2,4]]
解释:可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]

示例 2:

1
2
3
输入:["bat","tab","cat"]
输出:[[0,1],[1,0]]
解释:可拼接成的回文串为 ["battab","tabbat"]

思路:

对于字符串s1s2,若s1 + s2能组成回文串,那么有以下三种情况:

  1. len_s1 = len_s2,那么s1的翻转就是s2
  2. len_s1 > len_s2,那么s1能分成两个部分t1, t2。其中t1的翻转为s2t2为回文串。
  3. len_s1 < len_s2,那么s2能分成两个部分t1, t2。其中t1的翻转为s1t2为回文串。

所以我们首先定义一个哈希表,将每个单词的翻转映射为单词的索引下标。

然后对于每个单词,我们尝试找到一个切割点j,使左右两部分至少有一部分为回文串。

  1. 若左部分words[0 ... j - 1]为回文串,那么我们就尝试在哈希表中找到右部分的翻转,下标记为right_id,那么words[right_id] + words[i]为回文串,并将下标压入答案数组。

  2. 若右部分words[j ... m - 1]为回文串(m为单词的长度),那么我们就尝试在哈希表中找到左部分的翻转,下标记为left_id,那么words[i] + words[left_id]为回文串,并将下标压入答案数组。

tips:

  • 对于判断字符串是否为回文串的函数judge(),需要注意函数实现中循环的条件参数,不要弄错。
  • 为了数组的去重,压入数组前需要经过check()函数的判断。
  • 因为找的是不同的索引对,所以right_id, left_id不能等于i本身。
  • 默认空字符串也为回文串。

代码如下:

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Solution {
public:

vector<vector<int>> res;
unordered_map<string, int> words_reverse;

//回文串判断函数
bool judge(string& s, int left, int right){

int len = right - left + 1;

for(int i = 0; i < len / 2; i++){

if(s[i + left] != s[left + len - i - 1])
return false;
}

return true;
}

//在哈希表中寻找字符串的翻转
int find_reverse_word(string& s, int left, int right){

string find_str = s.substr(left, right - left + 1);

if(words_reverse.count(find_str))
return words_reverse[find_str];
else
return -1;
}

//检查重复
bool check(int i, int j){

for(int k = 0; k < res.size(); k++){

if(res[k][0] == i && res[k][1] == j)
return false;
}
return true;
}

vector<vector<int>> palindromePairs(vector<string>& words) {

for(int i = 0; i < words.size(); i++){

string temp = words[i];

reverse(temp.begin(), temp.end());
words_reverse[temp] = i;
}

for(int i = 0; i < words.size(); i++){

int m = words[i].size();
for(int j = 0; j <= m; j++){

if(judge(words[i], 0, j - 1)){ //左半部为回文串

int right_id = find_reverse_word(words[i], j, m - 1);

if(right_id != -1 && right_id != i){

if(check(right_id, i)) //去重
res.push_back({right_id, i});
}
}

if(judge(words[i], j, m - 1)){ //右半部为回文串

int left_id = find_reverse_word(words[i], 0, j - 1);

if(left_id != -1 && left_id != i){

if(check(i, left_id)) //去重
res.push_back({i, left_id});
}
}
}
}

return res;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: