题目链接：回文对
给定一组唯一的单词， 找出所有*不同* 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
示例 1:
输入: ["abcd","dcba","lls","s","sssll"]
输出: [[0,1],[1,0],[3,2],[2,4]]
解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2:
输入: ["bat","tab","cat"]
输出: [[0,1],[1,0]]
解释: 可拼接成的回文串为 ["battab","tabbat"]
思路
- 枚举所有的串，利用某种数据结构，存储后缀是否存在
- 对于每个串，假设一个串的取值范围是
[0,m-1]，以 j为界，把串分成两个子串 [0,j-1]和 [j,m-1]
- 处理这两个子串，如果
[0,j-1]是回文串，那么只需要找到 [j,m-1]这个串的镜像串，这样就可以组成一个大回文串。同理 [j,m-1]回文，那么只需要找到 [0,j-1]的镜像串，保存答案即可。
对于存储后缀，可以用哈希也可以用字典树，对于这种如果数据量太大的话，无意字典树更节省空间。
本代码采用标程中给的字典树。
代码
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:
struct node
{
int ch[26];
int flag;
node()
{
flag = -1;
memset(ch, 0, sizeof(ch));
}
};
vector<node> tree;
void insert(string &s, int id)
{
int len = s.length(), add = 0;
for (int i = 0; i < len; i++)
{
int x = s[i] - 'a';
if (!tree[add].ch[x])
{
tree.push_back(node());
tree[add].ch[x] = tree.size() - 1;
}
add = tree[add].ch[x];
}
tree[add].flag = id;
}
int findWord(string &s, int left, int right)
{
int add = 0;
for (int i = right; i >= left; i--)
{
int x = s[i] - 'a';
if (!tree[add].ch[x])
{
return -1;
}
add = tree[add].ch[x];
}
return tree[add].flag;
}
bool isPalindrome(string &s, int l, int r)
{
while (l < r)
if (s[l++] != s[r--])
return false;
return true;
}
vector<vector<int>> palindromePairs(vector<string> &words)
{
tree.push_back(node());
int n = words.size();
for (int i = 0; i < n; i++)
insert(words[i], i);
vector<vector<int>> ret;
for (int i = 0; i < n; i++)
{
int m = words[i].size();
for (int j = 0; j <= m; j++)
{
if (isPalindrome(words[i], j, m - 1))
{
int left_id = findWord(words[i], 0, j - 1);
if (left_id != -1 && left_id != i)
ret.push_back({i, left_id});
}
if (j && isPalindrome(words[i], 0, j - 1))
{
int right_id = findWord(words[i], j, m - 1);
if (right_id != -1 && right_id != i)
ret.push_back({right_id, i});
}
}
}
return ret;
}
};
|
最后修改于 2020-08-06
本作品采用
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。