国内虚拟助手网站成都关键词优化平台

前言

题目：647. 回文子串

参考题解：回文子串-代码随想录

提交代码

看到这道题目，如果不考虑时间复杂度，使用回溯遍历所以子集元素，进而判断这些元素是否为回文。(但这个方法无法保证连续)

既然要保证连续，回文由两端构成，直接暴力遍历两端的组合。时间复杂度为O(n^3)。

动态规划

想不到，以后再做一次也想不到用动态规划。这次的动态规划，不像传统的动态的规划，是个填充全部的二维数组。本次动态规划仅仅填充二维数组中的一部分。

下面代码，来自参考题解。

class Solution {
public:int countSubstrings(string s) {// 动态规划。dp[i,j]表示[i,j]范围是否为回文串。// if s[i] == s[j] ,是否为回文串，由dp[i+1][j-1]决定// if s[i] != s[j], 不是回文串vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));int result = 0;for(int i=s.size()-1; i>=0; i--){for(int j=i; j<s.size(); j++){if(s[i] == s[j]){if(j-i <= 1){ // 只有一个或两个元素result++;dp[i][j] = true;}else if(dp[i+1][j-1]){result++;dp[i][j] = true;}}}}return result;}
};

中心扩展

选择一个中心，向两端扩展，来判断以该中心的子字符串，有多少个是回文。难点在于，中心点可以是一个，也可以是两个。

下面代码，来自参考题解。

class Solution {
public:int countSubstrings(string s) {int result = 0;for (int i = 0; i < s.size(); i++) {result += extend(s, i, i, s.size()); // 以i为中心result += extend(s, i, i + 1, s.size()); // 以i和i+1为中心}return result;}int extend(const string& s, int i, int j, int n) {int res = 0;while (i >= 0 && j < n && s[i] == s[j]) {i--;j++;res++;}return res;}
};