[leetcode] 1332. Remove Palindromic Subsequences

[leetcode] 1332. Remove Palindromic Subsequences

Description

Given a string s consisting only of letters ‘a’ and ‘b’. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string, if it is generated by deleting some characters of a given string without changing its order.

A string is called palindrome if is one that reads the same backward as well as forward.

Example 1:

Input: s = "ababa"Output: 1Explanation: String is already palindrome

Example 2:

Input: s = "abb"Output: 2Explanation: "abb" -> "bb" -> "". Remove palindromic subsequence "a" then "bb".

Example 3:

Input: s = "baabb"Output: 2Explanation: "baabb" -> "b" -> "". Remove palindromic subsequence "baab" then "b".

Example 4:

Input: s = ""Output: 0

Constraints:

0 <= s.length <= 1000s only consists of letters ‘a’ and ‘b’

分析

题目的意思是：移除字符串的回文子串，直至为空串。这里有个规律，就是回文子串只由a，b组成，所以最多2次就能把原来的字符串变为空串，所以如果s字符串本身为空串的话，返回0；如果s本身就是回文子串的话，则返回1；否则返回2.如果发现这个规律，代码就比较简单了。

代码

class Solution: def removePalindromeSub(self, s: str) -> int: return 2-(s==s[::-1])-(s=='')

参考文献

​​[LeetCode] [Java/C++/Python] Maximum 2 Operations​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。