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

創(chuàng)新互聯(lián)建站10多年成都企業(yè)網(wǎng)站定制服務(wù);為您提供網(wǎng)站建設(shè),網(wǎng)站制作,網(wǎng)頁設(shè)計(jì)及高端網(wǎng)站定制服務(wù),成都企業(yè)網(wǎng)站定制及推廣,對(duì)軟裝設(shè)計(jì)等多個(gè)領(lǐng)域擁有豐富的網(wǎng)站運(yùn)維經(jīng)驗(yàn)的網(wǎng)站建設(shè)公司。

Palindromic Substrings 回文子字符串

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

1. The input string length won"t exceed 1000.

這道題給了一個(gè)字符串，讓我們計(jì)算有多少個(gè)回文子字符串。博主看到這個(gè)題，下意識(shí)的想著應(yīng)該是用 DP 來做，哼哼哧哧寫了半天，修修補(bǔ)補(bǔ)，終于通過了，但是博主寫的 DP 不是最簡便的方法，略顯復(fù)雜，這里就不貼了。還是直接講解大神們的解法好了。其實(shí)這道題也可以用遞歸來做，而且思路非常的簡單粗暴。就是以字符串中的每一個(gè)字符都當(dāng)作回文串中間的位置，然后向兩邊擴(kuò)散，每當(dāng)成功匹配兩個(gè)左右兩個(gè)字符，結(jié)果 res 自增1，然后再比較下一對(duì)。注意回文字符串有奇數(shù)和偶數(shù)兩種形式，如果是奇數(shù)長度，那么i位置就是中間那個(gè)字符的位置，所以左右兩遍都從i開始遍歷；如果是偶數(shù)長度的，那么i是最中間兩個(gè)字符的左邊那個(gè)，右邊那個(gè)就是 i+1，這樣就能 cover 所有的情況啦，而且都是不同的回文子字符串，參見代碼如下：

解法一：

class Solution {
public:
    int countSubstrings(string s) {
        if (s.empty()) return 0;
        int n = s.size(), res = 0;
        for (int i = 0; i < n; ++i) {
            helper(s, i, i, res);
            helper(s, i, i + 1, res);
        }
        return res;
    }
    void helper(string s, int i, int j, int& res) {
        while (i >= 0 && j < s.size() && s[i] == s[j]) {
            --i; ++j; ++res;
        }
    }
};

在剛開始的時(shí)候博主提到了自己寫的 DP 的方法比較復(fù)雜，為什么呢，因?yàn)椴┲鞯?dp[i][j] 定義的是范圍 [i, j] 之間的子字符串的個(gè)數(shù)，這樣其實(shí)還需要一個(gè)二維數(shù)組來記錄子字符串 [i, j] 是否是回文串，那還不如直接就將 dp[i][j] 定義成子字符串 [i, j] 是否是回文串就行了，然后i從 n-1 往0遍歷，j從i往 n-1 遍歷，然后看 s[i] 和 s[j] 是否相等，這時(shí)候需要留意一下，有了 s[i] 和 s[j] 相等這個(gè)條件后，i和j的位置關(guān)系很重要，如果i和j相等了，則 dp[i][j] 肯定是 true；如果i和j是相鄰的，那么 dp[i][j] 也是 true；如果i和j中間只有一個(gè)字符，那么 dp[i][j] 還是 true；如果中間有多余一個(gè)字符存在，則需要看 dp[i+1][j-1] 是否為 true，若為 true，那么 dp[i][j] 就是 true。賦值 dp[i][j] 后，如果其為 true，結(jié)果 res 自增1，參見代碼如下：

解法二：

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size(), res = 0;
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]);
                if (dp[i][j]) ++res;
            }
        }
        return res;
    }
};

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

分享標(biāo)題：C++如何實(shí)現(xiàn)回文子字符串
標(biāo)題鏈接：http://www.chinadenli.net/article38/iehpsp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、網(wǎng)站設(shè)計(jì)公司、服務(wù)器托管、Google、定制開發(fā)、企業(yè)網(wǎng)站制作

廣告

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