C++如何解決最長(zhǎng)回文子串問題

這篇文章主要介紹“C++如何解決最長(zhǎng)回文子串問題”的相關(guān)知識(shí)，小編通過實(shí)際案例向大家展示操作過程，操作方法簡(jiǎn)單快捷，實(shí)用性強(qiáng)，希望這篇“C++如何解決最長(zhǎng)回文子串問題”文章能幫助大家解決問題。

創(chuàng)新互聯(lián)建站是一家網(wǎng)站設(shè)計(jì)公司，集創(chuàng)意、互聯(lián)網(wǎng)應(yīng)用、軟件技術(shù)為一體的創(chuàng)意網(wǎng)站建設(shè)服務(wù)商，主營(yíng)產(chǎn)品：成都響應(yīng)式網(wǎng)站建設(shè)公司、成都品牌網(wǎng)站建設(shè)、成都全網(wǎng)營(yíng)銷。我們專注企業(yè)品牌在網(wǎng)站中的整體樹立，網(wǎng)絡(luò)互動(dòng)的體驗(yàn)，以及在手機(jī)等移動(dòng)端的優(yōu)質(zhì)呈現(xiàn)。成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)、移動(dòng)互聯(lián)產(chǎn)品、網(wǎng)絡(luò)運(yùn)營(yíng)、VI設(shè)計(jì)、云產(chǎn)品.運(yùn)維為核心業(yè)務(wù)。為用戶提供一站式解決方案，我們深知市場(chǎng)的競(jìng)爭(zhēng)激烈，認(rèn)真對(duì)待每位客戶，為客戶提供賞析悅目的作品，網(wǎng)站的價(jià)值服務(wù)。

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

這道題讓我們求最長(zhǎng)回文子串，首先說下什么是回文串，就是正讀反讀都一樣的字符串，比如 "bob", "level", "noon" 等等。那么最長(zhǎng)回文子串就是在一個(gè)字符串中的那個(gè)最長(zhǎng)的回文子串。LeetCode 中關(guān)于回文串的題共有五道，除了這道，其他的四道為 Palindrome Number，Validate Palindrome，Palindrome Partitioning，Palindrome Partitioning II，我們知道傳統(tǒng)的驗(yàn)證回文串的方法就是兩個(gè)兩個(gè)的對(duì)稱驗(yàn)證是否相等，那么對(duì)于找回文字串的問題，就要以每一個(gè)字符為中心，像兩邊擴(kuò)散來尋找回文串，這個(gè)算法的時(shí)間復(fù)雜度是 O(n*n)，可以通過 OJ，就是要注意奇偶情況，由于回文串的長(zhǎng)度可奇可偶，比如 "bob" 是奇數(shù)形式的回文，"noon" 就是偶數(shù)形式的回文，兩種形式的回文都要搜索，對(duì)于奇數(shù)形式的，我們就從遍歷到的位置為中心，向兩邊進(jìn)行擴(kuò)散，對(duì)于偶數(shù)情況，我們就把當(dāng)前位置和下一個(gè)位置當(dāng)作偶數(shù)行回文的最中間兩個(gè)字符，然后向兩邊進(jìn)行搜索，參見代碼如下：

解法一：

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() < 2) return s;
        int n = s.size(), maxLen = 0, start = 0;
        for (int i = 0; i < n - 1; ++i) {
            searchPalindrome(s, i, i, start, maxLen);
            searchPalindrome(s, i, i + 1, start, maxLen);
        }
        return s.substr(start, maxLen);
    }
    void searchPalindrome(string s, int left, int right, int& start, int& maxLen) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left; ++right;
        }
        if (maxLen < right - left - 1) {
            start = left + 1;
            maxLen = right - left - 1;
        }
    }
};

我們也可以不使用子函數(shù)，直接在一個(gè)函數(shù)中搞定，我們還是要定義兩個(gè)變量 start 和 maxLen，分別表示最長(zhǎng)回文子串的起點(diǎn)跟長(zhǎng)度，在遍歷s中的字符的時(shí)候，我們首先判斷剩余的字符數(shù)是否小于等于 maxLen 的一半，是的話表明就算從當(dāng)前到末尾到子串是半個(gè)回文串，那么整個(gè)回文串長(zhǎng)度最多也就是 maxLen，既然 maxLen 無法再變長(zhǎng)了，計(jì)算這些就沒有意義，直接在當(dāng)前位置 break 掉就行了。否則就要繼續(xù)判斷，我們用兩個(gè)變量 left 和 right 分別指向當(dāng)前位置，然后我們先要做的是向右遍歷跳過重復(fù)項(xiàng)，這個(gè)操作很必要，比如對(duì)于 noon，i在第一個(gè)o的位置，如果我們以o為最中心往兩邊擴(kuò)散，是無法得到長(zhǎng)度為4的回文串的，只有先跳過重復(fù)，此時(shí)left指向第一個(gè)o，right指向第二個(gè)o，然后再向兩邊擴(kuò)散。而對(duì)于 bob，i在第一個(gè)o的位置時(shí)，無法向右跳過重復(fù)，此時(shí) left 和 right 同時(shí)指向o，再向兩邊擴(kuò)散也是正確的，所以可以同時(shí)處理奇數(shù)和偶數(shù)的回文串，之后的操作就是更新 maxLen 和 start 了，跟上面的操作一樣，參見代碼如下：

解法二：

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() < 2) return s;
        int n = s.size(), maxLen = 0, start = 0;
        for (int i = 0; i < n;) {
            if (n - i <= maxLen / 2) break;
            int left = i, right = i;
            while (right < n - 1 && s[right + 1] == s[right]) ++right;
            i = right + 1;
            while (right < n - 1 && left > 0 && s[right + 1] == s[left - 1]) {
                ++right; --left;
            }
            if (maxLen < right - left + 1) {
                maxLen = right - left + 1;
                start = left;
            }
        }
        return s.substr(start, maxLen);
    }
};

此題還可以用動(dòng)態(tài)規(guī)劃 Dynamic Programming 來解，根 Palindrome Partitioning II 的解法很類似，我們維護(hù)一個(gè)二維數(shù)組 dp，其中 dp[i][j] 表示字符串區(qū)間 [i, j] 是否為回文串，當(dāng) i = j 時(shí)，只有一個(gè)字符，肯定是回文串，如果 i = j + 1，說明是相鄰字符，此時(shí)需要判斷 s[i] 是否等于 s[j]，如果i和j不相鄰，即 i - j >= 2 時(shí)，除了判斷 s[i] 和 s[j] 相等之外，dp[i + 1][j - 1] 若為真，就是回文串，通過以上分析，可以寫出遞推式如下：

dp[i, j] = 1 if i == j

= s[i] == s[j] if j = i + 1

= s[i] == s[j] && dp[i + 1][j - 1] if j > i + 1

這里有個(gè)有趣的現(xiàn)象就是如果我把下面的代碼中的二維數(shù)組由 int 改為 vector<vector<int>> 后，就會(huì)超時(shí)，這說明 int 型的二維數(shù)組訪問執(zhí)行速度完爆 std 的 vector 啊，所以以后盡可能的還是用最原始的數(shù)據(jù)類型吧。

解法三：

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        int n = s.size(), dp[n][n] = {0}, left = 0, len = 1;
        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1;
            for (int j = 0; j < i; ++j) {
                dp[j][i] = (s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1]));
                if (dp[j][i] && len < i - j + 1) {
                    len = i - j + 1;
                    left = j;
                }
            }
        }
        return s.substr(left, len);
    }
};

最后要來的就是大名鼎鼎的馬拉車算法 Manacher"s Algorithm，這個(gè)算法的神奇之處在于將時(shí)間復(fù)雜度提升到了 O(n) 這種逆天的地步，而算法本身也設(shè)計(jì)的很巧妙，很值得我們掌握，參見我另一篇專門介紹馬拉車算法的博客 Manacher"s Algorithm 馬拉車算法，代碼實(shí)現(xiàn)如下：

解法四：

class Solution {
public:
    string longestPalindrome(string s) {
        string t ="$#";
        for (int i = 0; i < s.size(); ++i) {
            t += s[i];
            t += "#";
        }
        int p[t.size()] = {0}, id = 0, mx = 0, resId = 0, resMx = 0;
        for (int i = 1; i < t.size(); ++i) {
            p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
            while (t[i + p[i]] == t[i - p[i]]) ++p[i];
            if (mx < i + p[i]) {
                mx = i + p[i];
                id = i;
            }
            if (resMx < p[i]) {
                resMx = p[i];
                resId = i;
            }
        }
        return s.substr((resId - resMx) / 2, resMx - 1);
    }
};

關(guān)于“C++如何解決最長(zhǎng)回文子串問題”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。

名稱欄目：C++如何解決最長(zhǎng)回文子串問題
轉(zhuǎn)載注明：http://bm7419.com/article10/igicdo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動(dòng)態(tài)網(wǎng)站、虛擬主機(jī)、品牌網(wǎng)站建設(shè)、網(wǎng)站排名、商城網(wǎng)站、微信公眾號(hào)

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

猜你還喜歡下面的內(nèi)容