本文主要是介绍【微软算法面试高频题】回文对，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

微软和谷歌的几个大佬组织了一个面试刷题群，可以加管理员VX：sxxzs3998（备注CSDN），进群参与讨论和直播

1. 题目

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

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

示例 2：
输入：words = ["bat","tab","cat"]
输出：[[0,1],[1,0]] 
解释：可拼接成的回文串为 ["battab","tabbat"]

示例 3：
输入：words = ["a",""]
输出：[[0,1],[1,0]]

2. 解析

本题可以使用暴力做法，即美剧每一对字符串的组合，暴力判断他们是否能够构成回文串，时间复杂度 O ( n 2 ∗ m ) O(n^2*m) O(n2∗m)，其中 n n n是字符串数量， m m m是字符串平均长度。但是很显然，这样的时间复杂度在实际工程中效率很低。

假设存在两个字符串 s 1 s_1 s1​和 s 2 s_2 s2​， s 1 + s 2 s_1+s_2 s1​+s2​是一个回文串，其中两个字符串的长度分别为 l e n 1 len_1 len1​和 l e n 2 len_2 len2​： 1）如果 l e n 1 = l e n 2 len_1=len_2 len1​=len2​, 那么 s 1 s_1 s1​是 s 2 s_2 s2​的翻转。 2）如果 l e n 1 > l e n 2 len_1>len_2 len1​>len2​，这种情况下可以将 s 1 s_1 s1​拆分成两部分 t 1 t_1 t1​和 t 2 t_2 t2​，其中 t 1 t_1 t1​是 s 2 s_2 s2​的翻转， t 2 t_2 t2​是一个回文串 3）如果 l e n 1 < l e n 2 len_1 < len_2 len1​<len2​, 这种情况下将 s 2 s_2 s2​拆分成两部分 t 1 t_1 t1​和 t 2 t_2 t2​, 其中 t 2 t_2 t2​是 s 1 s_1 s1​的翻转， t 1 t_1 t1​是一个回文串

所以，当面对两个字符串，可以将两个字符串中较长的那一个拿出来，拆分成两部分， t 1 t_1 t1​和 t 2 t_2 t2​：

• 当 t 1 t_1 t1​是回文串的时候，符合情况3），只需要去检验 t 2 t_2 t2​字符串是否包含翻转
• 当 t 2 t_2 t2​是回文串的时候，符合情况2），只需要去检验 t 1 t_1 t1​字符串是否包含翻转

所以，这就相当于要对每一个字符串都查询是否包含有回文串，然后将剩余的部分翻转并和其他字符串相匹配。对此，有两种实现方法：

• 我们可以使用字典树存储所有的字符串。在进行查询时，我们将待查询串的子串逆序地在字典树上进行遍历，即可判断其是否存在。
• 我们可以使用哈希表存储所有字符串的翻转串。在进行查询时，我们判断带查询串的子串是否在哈希表中出现，就等价于判断了其翻转是否存在。

其中字典树又称单词查找树、前缀树，是一种树形结构，利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，比哈希表更快。根节点不包含字符，除根节点外每个节点都只包含一个字符；从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；每个节点的所有子节点包含的字符都不相同。

一个简单的示例如下： 1)构建字典树

2）查找字符串"a"

所以，思路如下：

• 构建
  字符串取反；
  遍历word，创建节点；
  word.substring(j+1)为回文，则添加到该节点的suffixs列表中；这里要注意word本身为回文则添加到root节点的suffixs列表中；
• 查找
  遍历word；
  如果word.substring(j)为回文，则要看当前节点是否为一个单词，如果是，添加到结果中；对应情况3）
  word遍历结束且有以word结尾的单词，则要看当前节点的suffixs列表；对应情况2）

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.emplace_back();
                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 left, int right) {
        int len = right - left + 1;
        for (int i = 0; i < len / 2; i++) {
            if (s[left + i] != s[right - i]) {
                return false;
            }
        }
        return true;
    }

    vector<vector<int>> palindromePairs(vector<string>& words) {
        tree.emplace_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;
    }
};

哈希表

class Solution {
private:
    vector<string> wordsRev;
    unordered_map<string_view, int> indices;

public:
    int findWord(const string_view& s, int left, int right) {
        auto iter = indices.find(s.substr(left, right - left + 1));
        return iter == indices.end() ? -1 : iter->second;
    }

    bool isPalindrome(const string_view& s, int left, int right) {
        int len = right - left + 1;
        for (int i = 0; i < len / 2; i++) {
            if (s[left + i] != s[right - i]) {
                return false;
            }
        }
        return true;
    }

    vector<vector<int>> palindromePairs(vector<string>& words) {
        int n = words.size();
        for (const string& word: words) {
            wordsRev.push_back(word);
            reverse(wordsRev.back().begin(), wordsRev.back().end());
        }
        for (int i = 0; i < n; ++i) {
            indices.emplace(wordsRev[i], i);
        }

        vector<vector<int>> ret;
        for (int i = 0; i < n; i++) {
            int m = words[i].size();
            if (!m) {
                continue;
            }
            string_view wordView(words[i]);
            for (int j = 0; j <= m; j++) {
                if (isPalindrome(wordView, j, m - 1)) {
                    int left_id = findWord(wordView, 0, j - 1);
                    if (left_id != -1 && left_id != i) {
                        ret.push_back({i, left_id});
                    }
                }
                if (j && isPalindrome(wordView, 0, j - 1)) {
                    int right_id = findWord(wordView, j, m - 1);
                    if (right_id != -1 && right_id != i) {
                        ret.push_back({right_id, i});
                    }
                }
            }
        }
        return ret;
    }
};

• 时间复杂度： O ( n ∗ m 2 ) O(n*m^2) O(n∗m2)，其中 n n n是字符串的数量， m m m是字符串的平均长度。对于每一个字符串，我们需要 O ( m 2 ) O(m^2) O(m2)地判断其所有前缀与后缀是否是回文串，并 O ( m 2 ) O(m^2) O(m2)地寻找其所有前缀与后缀是否在给定的字符串序列中出现。
• 空间复杂度： O ( n × m ) O(n×m) O(n×m)，其中 n 是字符串的数量，m 是字符串的平均长度为字典树的空间开销。

微软和谷歌的几个大佬组织了一个面试刷题群，可以加管理员VX：sxxzs3998（备注CSDN），进群参与讨论和直播

这篇关于【微软算法面试高频题】回文对的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！