力扣（LeetCode）336.回文对（2022.12.03）-创新互联

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

创新互联公司一直秉承“诚信做人，踏实做事”的原则，不欺瞒客户，是我们最起码的底线！ 以服务为基础，以质量求生存，以技术求发展，成交一个客户多一个朋友！为您提供网站制作、成都网站制作、成都网页设计、成都微信小程序、成都网站开发、成都网站制作、成都软件开发、重庆APP软件开发是成都本地专业的网站建设和网站设计公司，等你一起来见证！

示例 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]]

提示：

1<= words.length<= 5000
0<= words[i].length<= 300
words[i] 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-pairs

方法一：字典树

C++提交内容：

// 双指针判断是否是回文： 这里直接用字符串加范围，减少字符串临时创建
bool IsPalindrome(const string& s, int i, int j)
{while (i< j)
    {if (s[i] != s[j])
        {return false;
        }
        ++i;
        --j;
    }
    return true;
}

// 字典树的结点，目前就是26个字母来构建
struct Node
{Node* children[26];
    // 当前节点的包含完整单词的序号
    vectorwords;
    // 当前节点之后部分字符串能构成回文串的序号
    vectorsuffixs;

    Node()
    {memset(children, 0, sizeof(children));
    }
};

class Solution {public:
    vector>palindromePairs(vector& words) {Node* root = new Node();

        int n = words.size();
        // 基于逆序构建字典树
        for (int i = 0; i< n; ++i)
        {// 反序番茨
            string revWord = words[i];
            reverse(revWord.begin(), revWord.end());

            Node* curr = root;
            int nj = revWord.size();
            // 当前单词就可以构成回文串，则插入到suffix里面
            if (IsPalindrome(revWord, 0, nj-1))
            {curr->suffixs.push_back(i);
            }
            for (int j = 0; j< nj; ++j)
            {int c = revWord[j] - 'a';
                if (curr->children[c] == nullptr)
                {curr->children[c] = new Node();
                }
                curr = curr->children[c];
                // 判断后续 j+1~n部分是否可以构成回文串
                if (IsPalindrome(revWord, j+1, nj-1))
                {curr->suffixs.push_back(i);
                }
            }
            // 表示这个节点对应于单词i的结束
            curr->words.push_back(i);
        }

        vector>res;

        // 再次正序遍历来获取回文串对
        for (int i = 0; i< n; ++i)
        {Node* curr = root;
            int j = 0;
            int nj = words[i].size();
            for (; j< nj; ++j)
            {// 判断后续是否已经是回文 ，那么就可以和当前节点 words 构成回文串，等同于模式 A1+A2+B 
                if (IsPalindrome(words[i], j, nj-1))
                {// 记得排除自己的序号
                    for (int k : curr->words)
                    {if (k != i)
                        {res.push_back({i, k});
                        }
                    }
                }
                // 找下一个结点，如果找不到则失败，直接break
                int c = words[i][j] - 'a';
                if (curr->children[c] == nullptr)
                {break;
                }
                curr = curr->children[c];
            }

            // 这里只考虑完全遍历完的情况，去找模式 A+B1+B2的情况来构建回文串
            if (j == nj)
            {for (int k : curr->suffixs)
                {if (k != i)
                    {res.push_back({i,k});
                    }
                }
            }
        }

        return res;
    }
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章名称：力扣（LeetCode）336.回文对（2022.12.03）-创新互联
标题链接：http://bzwzjz.com/article/djcedg.html