动态规划---回文子串

末蓝、 2022-05-23 07:57 210阅读 0赞

1、题目：

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".

2、解答：若选择一个，则以它为中心，比较它左右的元素是否相等。若选择两个，则比较这两个元素，并比较它左右的元素是否相等。

3、代码

C++代码

class Solution {
    public:
        int count = 0;
        int countSubstrings(string s) {
            if(s.length() == 0)
                return 0;
            
            for(int i=0;i<s.length();i++){
                extendPalindrome(s,i,i);        //选择一个中心点
                extendPalindrome(s,i,i+1);      //选择两个中心点  
            }
            return count;
            
        }
        
        void extendPalindrome(string s,int left,int right){
            while(left >= 0 && right < s.length() && s[left] == s[right]){
                count++;
                left--;
                right++;
            }
        }
    };

python代码的思路是：把该字符串的所有子串全部放在迭代器中。让后利用切片，判断是否相等

class Solution:
        def countSubstrings(self, s):
            """
            :type s: str
            :rtype: int
            """
            def getAllSubstring(string):
                l = (string[x:y] for x in range(len(string)) for y in range(x+1,len(string)+1)) #生成一个迭代器[[a],[ab],[abc],[b],...]
                return l
            sub_y = lambda x : x == x[::-1]
            
            count = 0
            for i in getAllSubstring(s):
                if sub_y(i):
                    count += 1
            return count