leetcode 1332. Remove Palindromic Subsequences（python）

描述

You are 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. Note that a subsequence does not necessarily need to be contiguous. A string is called palindrome if is one that reads the same backward as well as forward.

Example 1:

Input: s = "ababa"
Output: 1
Explanation: s is already a palindrome, so its entirety can be removed in a single step.

Example 2:

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

Example 3:

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

Note:

1 <= s.length <= 1000
s[i] is either 'a' or 'b'.

解析

根据题意，给定一个字符串 s ，只包含字母 'a' 和 'b' 。 在每一步的操作中可以从 s 中删除一个回文子序列。最后返回使给定字符串 s 为空的最小操作次数。

这道题如果不仔细分析题目，看起来会很难。你可能会使用暴力的解法，一个个去找出可能的回文子序列，然后每次删除最大的回文子序列，这样最后肯定能找出最小的操作次数。但是这是一道 Eazy 难度的题，肯定就是两三行代码就能解决的，不用如此麻烦。

这道题如果不仔细分析题目，看起来会很难。题目中已经说明了只包含两种字符，而且每次操作可以删除一个子序列，所以这就告诉了我们最多需要两次操作就能将 s 变成空字符串，因为第一次删除所有的 a 的子序列，第二次删除所有的 b 的子序列，当然如果一开始 s 中只有一种字符那就说明其本身就是回文字符串，最多需要 1 次就能将 s 变成空。

时间复杂度为 O(N) ，空间复杂度为 O(1) 。

解答

class Solution(object):
    def removePalindromeSub(self, s):
        """
        :type s: str
        :rtype: int
        """
        return 1 if s==s[::-1] else 2
	

运行结果

Runtime: 13 ms, faster than 94.74% of Python online submissions for Remove Palindromic Subsequences.
Memory Usage: 13.5 MB, less than 31.58% of Python online submissions for Remove Palindromic Subsequences.

原题链接

leetcode.com/problems/re…

您的支持是我最大的动力