LeetCode_双指针_简单_1332.删除回文子序列

痛定思痛。 2023-10-07 19:57 7阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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”。

**提示：**  
1 <= s.length <= 1000  
s 仅包含字母 ‘a’ 和 ‘b’

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/remove-palindromic-subsequences

## 2.思路 ##

（1）双指针  
由于字符串 s 仅包含字母 ‘a’ 和 ‘b’，并且**相同的字符组成的子序列一定是回文子序列**，因此如果该 s 本身为回文串，此时只需删除 1 次即可。如果 s 本身不是回文串，此时只需删除 2 次即可（比如可以先删除所有的 'a’，再删除所有的 ‘b’，删除次数为 2）。其中，在判断 s 是否为回文串时，可以使用双指针来进行判断。

相关题目：  
[LeetCode\_动态规划\_中等\_5.最长回文子串][LeetCode_5.]  
[LeetCode\_回溯\_动态规划\_中等\_131.分割回文串][LeetCode_131.]  
[LeetCode\_双指针\_简单\_234.回文链表][LeetCode_234.]  
[LeetCode\_贪心算法\_简单\_409.最长回文串][LeetCode_409.]  
[LeetCode\_动态规划\_中等\_516.最长回文子序列][LeetCode_516.]  
[LeetCode\_字符串\_中等\_647. 回文子串][LeetCode_647.]

## 3.代码实现（Java） ##

//思路1————双指针
    class Solution {
        
        public int removePalindromeSub(String s) {
        
            int length = s.length();
            for (int i = 0; i < length / 2; i++) {
        
                if (s.charAt(i) != s.charAt(length - 1 - i)) {
        
                    return 2;
                }
            }
            return 1;
        }
    }

[LeetCode_5.]: https://blog.csdn.net/weixin_43004044/article/details/118353990
[LeetCode_131.]: https://blog.csdn.net/weixin_43004044/article/details/125341429
[LeetCode_234.]: https://blog.csdn.net/weixin_43004044/article/details/122763107
[LeetCode_409.]: https://blog.csdn.net/weixin_43004044/article/details/126935075
[LeetCode_516.]: https://blog.csdn.net/weixin_43004044/article/details/126813021
[LeetCode_647.]: https://blog.csdn.net/weixin_43004044/article/details/124979183