淘宝客网站下载,网站建设淘宝客,广告收益平台,网站业务功能设计1. 题目
给你一个字符串 s#xff0c;它仅由字母 ‘a’ 和 ‘b’ 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。
返回删除给定字符串中所有字符#xff08;字符串为空#xff09;的最小删除次数。
「子序列」定义#xff1a;如果一个字符串可以通过删除原字符…1. 题目
给你一个字符串 s它仅由字母 ‘a’ 和 ‘b’ 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。
返回删除给定字符串中所有字符字符串为空的最小删除次数。
「子序列」定义如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到那么这个字符串就是原字符串的一个子序列。
「回文」定义如果一个字符串向后和向前读是一致的那么这个字符串就是一个回文。
示例 1
输入s ababa
输出1
解释字符串本身就是回文序列只需要删除一次。示例 2
输入s abb
输出2
解释abb - bb - .
先删除回文子序列 a然后再删除 bb。示例 3
输入s baabb
输出2
解释baabb - b - .
先删除回文子序列 baab然后再删除 b。示例 4
输入s
输出0提示
0 s.length 1000
s 仅包含字母 a 和 b来源力扣LeetCode 链接https://leetcode-cn.com/problems/remove-palindromic-subsequences 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
语文题回文子序列 先删除a再删除b最多2次
class Solution {
public:int removePalindromeSub(string s) {if(s.size() 1)return s.size();if(isPalindrome(s))return 1;return 2;}bool isPalindrome(string s) {int i 0, j s.size()-1;while(i j){if(s[i] ! s[j])return false;i;j--;}return true;}
};
