nuno-alberto-MykFFC5zolE-unsplash.jpg
简单给你一个字符串 s，它仅由字母 ‘a’ 和 ‘b’ 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。

返回删除给定字符串中所有字符（字符串为空）的最小删除次数。

「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。

「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。

示例 1：

输入：s = “ababa”
输出：1
解释：字符串本身就是回文序列，只需要删除一次。
示例 2：

输入：s = “abb”
输出：2
解释：”abb” -> “bb” -> “”.
先删除回文子序列 “a”，然后再删除 “bb”。
示例 3：

输入：s = “baabb”
输出：2
解释：”baabb” -> “b” -> “”.
先删除回文子序列 “baab”，然后再删除 “b”。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-palindromic-subsequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  5. var removePalindromeSub = function (s) {
  6.   if (s === [...s].reverse().join("")) {
  7.     return 1;
  8.   }
  9.   return 2;
  10. };

思路

题目说的是子序列而非子串，也就是说根本不用考虑字符串中回文子串的问题，举个例子：假设字符串baabb按照题意进行删除，baabb和baabb这两种删除方式都是可行的！
又根据题意，字符串只有a，b两个字符，所以最差的情况也不过就是先把a字符全部删除再把b字符全部删除，因为全部由a组成/全部由b组成的字符串肯定是回文字符串！而最好的情况就是题目所给的字符串本身就是个回文字符串，只需要一次就能删除完毕。