动态规划6.0
- 动态规划 - - - 回文子串问题
- 1. 回文子串
- 2. 最长回文子串
- 3. 分割回文串Ⅳ
- 4. 分割回文串Ⅱ
- 5. 最长回文子序列
- 6. 让字符串成为回文串的最少插入次数
动态规划 - - - 回文子串问题
1. 回文子串
题目链接 -> Leetcode -647.回文子串
(图片来源网络,侵删)Leetcode -647.回文子串
题目:给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。
(图片来源网络,侵删)回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。
示例 1:
输入:s = “abc”
输出:3
解释:三个回文子串 : “a”, “b”, “c”
示例 2:
输入:s = “aaa”
输出:6
解释:6个回文子串 : “a”, “a”, “a”, “aa”, “aa”, “aaa”
提示:
- 1 Leetcode -5.最长回文子串
Leetcode -5.最长回文子串
题目:给你一个字符串 s,找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
示例 1:
输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。
示例 2:
输入:s = “cbbd”
输出:“bb”
提示:
- 1 retlen)
{
retlen = j - i + 1;
begin = i;
}
}
}
return s.substr(begin, retlen);
}
};
3. 分割回文串Ⅳ
题目链接 -> Leetcode -1745.分割回文串Ⅳ
Leetcode -1745.分割回文串Ⅳ
题目:给你一个字符串 s ,如果可以将它分割成三个 非空 回文子字符串,那么返回 true ,否则返回 false 。
当一个字符串正着读和反着读是一模一样的,就称其为 回文字符串 。
示例 1:
输入:s = “abcbdd”
输出:true
解释:“abcbdd” = “a” + “bcb” + “dd”,三个子字符串都是回文的。
示例 2:
输入:s = “bcbddxy”
输出:false
解释:s 没办法被分割成 3 个回文子字符串。
提示:
- 3 Leetcode -132.分割回文串Ⅱ
Leetcode -132.分割回文串Ⅱ
题目:给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1:
输入:s = “aab”
输出:1
解释:只需一次分割就可将 s 分割成[“aa”, “b”] 这样两个回文子串。
示例 2:
输入:s = “a”
输出:0
示例 3:
输入:s = “ab”
输出:1
提示:
- 1 = 0; i--) { for(int j = i + 1; j
- 3 Leetcode -132.分割回文串Ⅱ
- 1 retlen)
{
retlen = j - i + 1;
begin = i;
}
}
}
return s.substr(begin, retlen);
}
};
- 1 Leetcode -5.最长回文子串