代码随想录第五十七天

代码随想录第五十七天

647. 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：“abc” 输出：3 解释：三个回文子串: “a”, “b”, “c”
示例 2：
输入：“aaa” 输出：6 解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
提示：
输入的字符串长度不会超过 1000 。
1、dp[i][j]:i-j左闭右闭区间是否为回文串
2、if s[i]==s[j]
i、j-i<=1
dp[i][j]=true
回文串数量++
ii、j-i>1
需要判断i+1~j-1左闭右闭区间是否是回文串
if dp[i+1][j-1]==true
dp[i][j]=true
回文串数量++
3、初始化
全部初始化为false
4、遍历外层逆序遍历，内层顺序遍历
5、模拟
代码如下：

int palindromeSubSeqence(string s)
	{
		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;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

516.最长回文子序列

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 1: 输入: “bbbab” 输出: 4 一个可能的最长回文子序列为 “bbbb”。
示例 2: 输入:“cbbd” 输出: 2 一个可能的最长回文子序列为 “bb”。
提示：
1 <= s.length <= 1000
s 只包含小写英文字母
1、dp[i][j]:i-j左闭右闭区回文子序列的最大长度
2、if s[i]s[j]
i、ji
dp[i][j]=1
回文串数量++
ii、j-i>=1
需要利用i+1~j-1左闭右闭区间的回文串的最大值
dp[i][j]=dp[j-1]+2
else
在i+1~j与 i ~j-1之间的回文序列中取最大值
dp[i][j]=max(dp[i][j-1],dp[i+1][j])
3、初始化
全部初始化为0
4、遍历外层逆序遍历，内层顺序遍历
5、模拟
代码如下：

int maxPalindromeSubSeqence(string s)
	{
		vector<vector<int>>dp(s.size(), vector<int>(s.size(), 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)
						dp[i][j] = 1;
					else 
					{
						dp[i][j] = dp[i + 1][j - 1] + 2;
					}
				}
				else
				{
					dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
				}
			}
			
		}
		return dp[0][s.size() - 1];
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25