【微软算法面试高频题】回文对 1 题目 2 解析

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

题目

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

c++复制代码示例 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]]

解析

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

假设存在两个字符串s1s_1s1和s2s_2s2，s1+s2s_1+s_2s1+s2是一个回文串，其中两个字符串的长度分别为len1len_1len1和len2len_2len2： 1）如果len1=len2len_1=len_2len1=len2, 那么s1s_1s1是s2s_2s2的翻转。 2）如果len1>len2len_1>len_2len1>len2，这种情况下可以将s1s_1s1拆分成两部分t1t_1t1和t2t_2t2，其中t1t_1t1是s2s_2s2的翻转，t2t_2t2是一个回文串 3）如果len1<len2len_1 < len_2len1<len2, 这种情况下将s2s_2s2拆分成两部分t1t_1t1和t2t_2t2, 其中t2t_2t2是s1s_1s1的翻转，t1t_1t1是一个回文串

所以，当面对两个字符串，可以将两个字符串中较长的那一个拿出来，拆分成两部分，t1t_1t1和t2t_2t2：

当t1t_1t1是回文串的时候，符合情况3），只需要去检验t2t_2t2字符串是否包含翻转
当t2t_2t2是回文串的时候，符合情况2），只需要去检验t1t_1t1字符串是否包含翻转

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

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

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

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

2）查找字符串”a”

所以，思路如下：

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

c++复制代码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;
    }
};

哈希表

c++复制代码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∗m2)O(n*m^2)O(n∗m2)，其中nnn是字符串的数量，mmm是字符串的平均长度。对于每一个字符串，我们需要O(m2)O(m^2)O(m2)地判断其所有前缀与后缀是否是回文串，并O(m2)O(m^2)O(m2)地寻找其所有前缀与后缀是否在给定的字符串序列中出现。
空间复杂度：O(n×m)O(n×m)O(n×m)，其中 n 是字符串的数量，m 是字符串的平均长度为字典树的空间开销。

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

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有