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.
原題連結
https://leetcode.com/problems/remove-palindromic-subsequences/
您的支援是我最大的動力
- linux 安裝 ES 8.0 和 kibana 8.0 爬米共坑
- ES 8.0 及其生態配置過程一條龍服務
- 2022 年中紀
- leetcode 1048. Longest String Chain(python)
- leetcode 1354. Construct Target Array With Multiple Sums(python)
- leetcode 2311. Longest Binary Subsequence Less Than or Equal to K(python)
- leetcode 2304. Minimum Path Cost in a Grid(python)
- leetcode 2303. Calculate Amount Paid in Taxes(python)
- 帶你輕鬆入門 Bert
- leetcode 1332. Remove Palindromic Subsequences(python)
- leetcode 3. Longest Substring Without Repeating Characters (python)
- leetcode 2296. Design a Text Editor (python)
- leetcode 2293. Min Max Game(python)
- leetcode 1584. Min Cost to Connect All Points(python)
- leetcode 318. Maximum Product of Word Lengths(python)
- 沙灘 美女才是夏天的正確開啟方式
- leetcode 2275. Largest Combination With Bitwise AND Greater Than Zero (python)
- leetcode 2258. Escape the Spreading Fire(python)
- leetcode 2257. Count Unguarded Cells in the Grid(python)
- leetcode 2273. Find Resultant Array After Removing Anagrams(python)