C++實現LeetCode(647.回文子字符串)

Posted on by

[LeetCode] 647. 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.

這道題給瞭一個字符串，讓我們計算有多少個回文子字符串。博主看到這個題，下意識的想著應該是用 DP 來做，哼哼哧哧寫瞭半天，修修補補，終於通過瞭，但是博主寫的 DP 不是最簡便的方法，略顯復雜，這裡就不貼瞭。還是直接講解大神們的解法好瞭。其實這道題也可以用遞歸來做，而且思路非常的簡單粗暴。就是以字符串中的每一個字符都當作回文串中間的位置，然後向兩邊擴散，每當成功匹配兩個左右兩個字符，結果 res 自增1，然後再比較下一對。註意回文字符串有奇數和偶數兩種形式，如果是奇數長度，那麼i位置就是中間那個字符的位置，所以左右兩遍都從i開始遍歷；如果是偶數長度的，那麼i是最中間兩個字符的左邊那個，右邊那個就是 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;
        }
    }
};

在剛開始的時候博主提到瞭自己寫的 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++實現LeetCode(647.回文子字符串)的文章就介紹到這瞭,更多相關C++實現回文子字符串內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：