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"]

思路：

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

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

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

然后对于每个单词，我们尝试找到一个切割点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. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网