給定一組 互不相同 的單詞， 找出所有 不同 的索引對 (i, j)，使得列表中的兩個單詞， words[i] + words[j] ，可拼接成回文串。

創(chuàng)新互聯(lián)公司一直秉承“誠信做人，踏實做事”的原則，不欺瞞客戶，是我們最起碼的底線！ 以服務(wù)為基礎(chǔ)，以質(zhì)量求生存，以技術(shù)求發(fā)展，成交一個客戶多一個朋友！為您提供網(wǎng)站制作、成都網(wǎng)站制作、成都網(wǎng)頁設(shè)計、成都微信小程序、成都網(wǎng)站開發(fā)、成都網(wǎng)站制作、成都軟件開發(fā)、重慶APP軟件開發(fā)是成都本地專業(yè)的網(wǎng)站建設(shè)和網(wǎng)站設(shè)計公司，等你一起來見證！

示例 1：

輸入：words = [“abcd”,“dcba”,“l(fā)ls”,“s”,“sssll”]
輸出：[[0,1],[1,0],[3,2],[2,4]]
解釋：可拼接成的回文串為 [“dcbaabcd”,“abcddcba”,“slls”,“l(fā)lssssll”]

示例 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++提交內(nèi)容：

// 雙指針判斷是否是回文： 這里直接用字符串加范圍，減少字符串臨時創(chuàng)建
bool IsPalindrome(const string& s, int i, int j)
{while (i< j)
    {if (s[i] != s[j])
        {return false;
        }
        ++i;
        --j;
    }
    return true;
}

// 字典樹的結(jié)點，目前就是26個字母來構(gòu)建
struct Node
{Node* children[26];
    // 當前節(jié)點的包含完整單詞的序號
    vectorwords;
    // 當前節(jié)點之后部分字符串能構(gòu)成回文串的序號
    vectorsuffixs;

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

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

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

            Node* curr = root;
            int nj = revWord.size();
            // 當前單詞就可以構(gòu)成回文串，則插入到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];
                // 判斷后續(xù) j+1~n部分是否可以構(gòu)成回文串
                if (IsPalindrome(revWord, j+1, nj-1))
                {curr->suffixs.push_back(i);
                }
            }
            // 表示這個節(jié)點對應(yīng)于單詞i的結(jié)束
            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)
            {// 判斷后續(xù)是否已經(jīng)是回文 ，那么就可以和當前節(jié)點 words 構(gòu)成回文串，等同于模式 A1+A2+B 
                if (IsPalindrome(words[i], j, nj-1))
                {// 記得排除自己的序號
                    for (int k : curr->words)
                    {if (k != i)
                        {res.push_back({i, k});
                        }
                    }
                }
                // 找下一個結(jié)點，如果找不到則失敗，直接break
                int c = words[i][j] - 'a';
                if (curr->children[c] == nullptr)
                {break;
                }
                curr = curr->children[c];
            }

            // 這里只考慮完全遍歷完的情況，去找模式 A+B1+B2的情況來構(gòu)建回文串
            if (j == nj)
            {for (int k : curr->suffixs)
                {if (k != i)
                    {res.push_back({i,k});
                    }
                }
            }
        }

        return res;
    }
};

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱：力扣（LeetCode）336.回文對（2022.12.03）-創(chuàng)新互聯(lián)
網(wǎng)頁地址：http://jinyejixie.com/article16/djcedg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、軟件開發(fā)、網(wǎng)站收錄、網(wǎng)站策劃、網(wǎng)站營銷

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)