LeetCode·647.回文子串·动态规划_回文子串 动态规划

链接：https://leetcode.cn/problems/palindromic-substrings/solution/chun-by-xun-ge-v-71qe/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
回文子串是正着读和倒过来读一样的字符串中的由连续字符组成的一个序列。子串是连续的，子序列是可以不连续的

计算有多少个回文子串的最朴素方法就是枚举出所有的回文子串，而枚举出所有的回文字串又有两种思路，分别是：

• 枚举出所有的子串，然后再判断这些子串是否是回文； -> 暴力求解
• 枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。 -> 中心扩展

• 暴力求解 

利用双指针和回文子串的基本性质，回文子串是正着读和倒过来读一样的字符串中的由连续字符组成的一个序列。
定义双指针遍历整个字符串，当s[i] == s[j]时，判断一下 i-j 是不是回文子串，是+1，不是+0
简单暴力，但是时间消耗比较大

• 动态规划

定义一个dp[n][m]数组，其中dp[i][j]表示从字符串下标 i开始到j 的子串是否为回文字符串，是则保存为1，不是保存为0
那么dp[i][j] 是不是回文字符串有两个条件

• s[i] == s[j]
• dp[i+1][j-1] 也是回文字符串

当i，j离的比较近时，dp[i+1][j-1]就不存在了，只需要满足第一个条件即可
那么递推公式我们就可以知道

for(int i = 0; i < strlen(s); i++){
    for(int j = i+1; j <strlen(s); j++){ 
        if(s[i] == s[j] && (j - i <=2  || dp[i + 1][j - 1] == 1)){
            dp[i][j] = 1;
        } else{
            dp[i][j] = 0;
        }
    }
}

但是如果我们从字符串开始位置更新dp数组，就会存在一个问题，当我们求dp[i][j]时，需要知晓dp[i + 1][j - 1]是否为回文串，但是 i+1 的位置我们还没有遍历到，所以我们需要改变一下遍历方向，从末尾开始遍历 

• 中心扩展

其实和暴力求解思路差不多，枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。

代码

暴力求解

int istrue(char * s,int left,int right){  //给定左右边界依次遍历，判断是否为回文子串
    while(left < right)//当为奇数中间不会被遍历到，当为偶数就都遍历到
    {
        if(s[left] != s[right])//只有其中有不相等，则不满足要求
        {
            return 0;
        }
        left++;
        right--;
    }
    return 1;
}
/*
*int countSubstrings(char * s)
int countSubstrings：判断字符串中的回文子串
char * s：字符串
返回值：回文子串的个数
*/
int countSubstrings(char * s){
   int len=strlen(s);
   int sum=len;  //由于单个字符可以看作是回文子串，所以初始值为元素个数
   for(int i=0;i<len;i++){
       for(int j=i+1;j<len;j++){
           if(s[i]==s[j]){
               sum=sum+istrue(s,i,j);//统计总数
           }
       }
   }
   return sum;
}
 
 
作者：xun-ge-v
链接：https://leetcode.cn/problems/palindromic-substrings/solution/chun-by-xun-ge-v-71qe/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

动态规划

/*
*int countSubstrings(char * s)
int countSubstrings：判断字符串中的回文子串
char * s：字符串
返回值：回文子串的个数
*/
int countSubstrings(char * s){
    int len = strlen(s);
    int dp[len][len];
    int i, j;
    int res = len;
    /* dp动态规划公式, 需要从下往上递推 */
    for (i = len - 1; i >= 0; i--) {
        for (j = i + 1; j < len; j++) {//因为i是先后，就是j向前，所有情况都会遍历到，比如一个情况字符
            if (s[i] == s[j] && (j - i <=2  || dp[i + 1][j - 1] == 1)) {//满足条件
                dp[i][j] = 1;
            }
            else//不满足条件
            {
                dp[i][j] = 0;
            }
            res += dp[i][j];
        }
    }
    return res;
}
 
作者：xun-ge-v
链接：https://leetcode.cn/problems/palindromic-substrings/solution/chun-by-xun-ge-v-71qe/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

中心扩展

/*
*int countSubstrings(char * s)
int countSubstrings：判断字符串中的回文子串
char * s：字符串
返回值：回文子串的个数
*/
int countSubstrings(char* s) {
    int n = strlen(s), ans = 0;
    for (int i = 0; i < 2 * n - 1; ++i) {
        int l = i / 2, r = i / 2 + i % 2;
        while (l >= 0 && r < n && s[l] == s[r]) {
            --l;
            ++r;
            ++ans;
        }
    }
    return ans;
}
 
作者：xun-ge-v
链接：https://leetcode.cn/problems/palindromic-substrings/solution/chun-by-xun-ge-v-71qe/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间空间复杂度