C++回文子字符串問題怎么解決

這篇文章主要介紹“C++回文子字符串問題怎么解決”，在日常操作中，相信很多人在C++回文子字符串問題怎么解決問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C++回文子字符串問題怎么解決”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

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:

The input string length won"t exceed 1000.

解法一：

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;
        }
    }
};

在剛開始的時候博主提到了自己寫的 DP 的方法比較復雜，為什么呢，因為博主的 dp[i][j] 定義的是范圍 [i, j] 之間的子字符串的個數，這樣其實還需要一個二維數組來記錄子字符串 [i, j] 是否是回文串，那還不如直接就將 dp[i][j] 定義成子字符串 [i, j] 是否是回文串就行了，然后i從 n-1 往0遍歷，j從i往 n-1 遍歷，然后看 s[i] 和 s[j] 是否相等，這時候需要留意一下，有了 s[i] 和 s[j] 相等這個條件后，i和j的位置關系很重要，如果i和j相等了，則 dp[i][j] 肯定是 true；如果i和j是相鄰的，那么 dp[i][j] 也是 true；如果i和j中間只有一個字符，那么 dp[i][j] 還是 true；如果中間有多余一個字符存在，則需要看 dp[i+1][j-1] 是否為 true，若為 true，那么 dp[i][j] 就是 true。賦值 dp[i][j] 后，如果其為 true，結果 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;
    }
};

到此，關于“C++回文子字符串問題怎么解決”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！