这是 2020 年 8 月 6 日 的每日一题。因为昨天断网了,今天补更新。这道题主要是涉及到一种新的数据结构 - 字典树。之后可能会写博客记录一下。现在先看题吧。

题目

给定一组 互不相同 的单词, 找出所有不同 的索引对(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"]

暴力解法(超时)

最简单也最好想的。双重循环遍历所有 ij 然后判断是否是回文串。

其中双重循环的时间复杂度为 NN 为单词数量。
判断是否为回文串时间复杂度为 LL 为单词平均长度。

o(N^2*L),肯定是超时的。

代码

  • 语言: C++
class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> result;
        for(int i = 0 ; i < words.size() ; i ++){
            for(int j = 0 ; j < words.size() ; j ++){
                if(i == j){
                    continue;
                }
                if(isPalindrome(words[i]+words[j])){
                    result.push_back({i,j});
                }
            }
        }
        return result;
    }

    bool isPalindrome(const string& word){
        int left = 0;
        int right = word.size()-1;
        while(right > left){
            if(word[left] != word[right]){
                return false;
            }
            left ++;
            right --;
        }
        return true;
    }
};

优化

判断条件

可以观察符合条件的字符串有什么特点。
假设一下两个字符串组合之后是回文串:

U3F2XA(<code>DL5ND9U@J4S</code>BB.png

我们会发现,其中较长的字符串等于较短的字符串反序加上另一个回文串:

G0MBF{1Y9%745FF2DM0H5N1.png

前后缀表

这里我们补充一下 前后缀表 的概念。就是一个字符串所有 前缀 或 后缀 组成的列表。

比如对于字符串 abcdd ,则它前缀列表为: [a, ab, abc, abcd, abcdd],后缀列表为: [d, dd, cdd, bcdd, abcdd]

还是很好理解的。

最终思路

有了以上铺垫,我们就可以整理出优化的解题思路了。首先遍历所有单词的前后缀。如果某个前后缀是回文串,则在剩下单词表中寻找这个单词除去这个前后缀后的逆串。找到了就是一对匹配了。

所以时间复杂度变成了两部分,第一部分是遍历所有前后缀,时间复杂度为 2LL 为单词平均长度。第二部分是判断前后缀是否是回文串,这里时间复杂度是 L。还有就是判断剩下部分的逆串是否在单词表中出现。这里可以使用 字典树哈希表。复杂度为 L^2。合在一起的复杂度为 o(N*L^2),题目里给出的字符串都是比较短的,所以要小于暴力解法。

代码 - 哈希表

  • 语言: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;
    }
};

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/palindrome-pairs/solution/hui-wen-dui-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

代码 - 字典树

有关于字典树,我可能会在下一篇博客更新。

  • 语言: 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;
    }
};

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/palindrome-pairs/solution/hui-wen-dui-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。