回文子串_牛客博客

题目难度：一星
考察点：回文字符串

方法1：暴力

1. 分析：

这个题我们首先看到的是字符串s的长度才不到50，所以可以使用最简单的暴力枚举就可以解决这个问题。这个问题可以拆分成如下两部分:
(1). 如何枚举字符串s的全部子串;
(2). 如何判断字符串是否为回文字符串。
对于第(1)部分来说，我们就直接利用两个指针i和j进行枚举，以i(0<=i<len(s))为子串起点，j(i<=j<len(s))为子串终点，对于第(2)部分来说，我们写一个函数判断是否为回文字符串，即第一个和最后一个字符比，第二个和倒数第二个比，即第i个和len(s)-i-1个比，如果都相等证明是回文字符串，否则不是。

算法实现:
(1). 输入字符数s，并获取长度len=s.size()
(2). 按照上述方法进行枚举所有子串,tmp表示区间[i,j]的子串
(3). 判断子串tmp是否为回文字符串，如果是回文字符串的话，结果ans++。
(4). 输出结果ans。

2. 复杂度分析：

时间复杂度：O(n^3)
空间复杂度：O(1)

3 代码：

#include <bits/stdc++.h>
using namespace std;
bool check(string s) {
 int len = s.size();
 for(int i=0; i<len/2; i++) if(s[i] != s[len-1-i]) return false;
 return true;
}
int main() {
 string s; cin>>s;
 int len = s.size(), ans = 0;
 for(int i=0; i<len; i++) {
     string tmp = "";
     for(int j=i; j<len; j++) {
         tmp += s[j];
         if(check(tmp)) ans++;
     }
 }
 cout<<ans<<endl;
 return 0;
}

方法2：动态规划

分析：
上述的暴力算法固然能够解决这个问题，但是我们还是考虑一个更优的算法，动态规划。设dp[i][j]表示区间[i,j]的子串是否为回文字符串，那么对于字符i和字符j就有两种可能：
(1). s[i] == s[j]，那么此时dp[i][j] = dp[i+1][j-1];
(2). s[i] != s[j], 那么此时dp[i][j] = false;
上面的情况是建立在j-i>=2的情况下，接下来还有两种情况：
(1). j-i==0，那么显然一个字符为回文，那么dp[i][j] = true;
(2). j-i==1，那么显然判断s[i]是否和s[j]相等，即dp[i][j] = (s[i]==s[j])。
综上，我们可以列出状态转移方程如下：
(1) j - i = 0 dp[i][j] = 1;
(2) j - i = 1 dp[i][j] = (s[i]==s[j]);
(3) j - i >= 2 dp[i][j] = (dp[i+1][j-1]==1&&s[i]==s[j]);
复杂度分析：
时间复杂度：O(n^2)
空间复杂度：O(n^2)

代码：

#include <bits/stdc++.h>
using namespace std;
int dp[55][55];
int main() {
 string s; cin>>s;
 int len = s.size(), ans = 0;
 for(int i=len-1; i>=0; i--) {
     for(int j=i; j<len; j++) {
         if(i == j) dp[i][j] = 1;
         else if(j-i==1) dp[i][j] = (s[i]==s[j]);
         else dp[i][j] = (dp[i+1][j-1]==1&&s[i]==s[j]);
         ans += dp[i][j];
     }
 }
 cout<<ans<<endl;
 return 0;
}

回文子串

题目难度：一星 考察点：回文字符串