leetcode 1332. Remove Palindromic Subsequences（python）

持續創作，加速成長！這是我參與「掘金日新計劃 · 6 月更文挑戰」的第20天，點選檢視活動詳情

描述

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.

原題連結

http://leetcode.com/problems/remove-palindromic-subsequences/

您的支援是我最大的動力