3

LeetCode 1653: 使字符串平衡的最少删除次数

 1 year ago
source link: https://yuxinli1.github.io/LeetCode-1653-%E4%BD%BF%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%B9%B3%E8%A1%A1%E7%9A%84%E6%9C%80%E5%B0%91%E5%88%A0%E9%99%A4%E6%AC%A1%E6%95%B0/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

给你一个字符串s，它仅包含字符'a'和'b'。

你可以删除s中任意数目的字符，使得s平衡。当不存在下标对(i,j)满足i<j，且s[i] = 'b'的同时s[j] = 'a'，此时认为s是平衡的。

请你返回使s平衡的最少删除次数。

解法一：动态规划

基本思路：

  • 如果字符串末尾是'a'，有两种选择：
    • 删除它，将0...n-1变为平衡；
    • 保留它，删除前面所有的'b'。
  • 如果字符串末尾是'b'，保留，将0...n-1变为平衡。

参考代码：

class Solution:
    def minimumDeletions(self, s: str) -> int:
        countB = 0
        dp = 0
        for c in s:
            if c == 'a':
                # dp+1: 删除末尾的'a'带来的操作; countB: 保留'a'删除前面所有的'b'
                dp = min(dp+1,countB)
            else:
                # 统计到当前位置为止字符串中'b'的数量
                countB += 1
        return dp

解法二：状态机DP

基本思路：

满足要求的字符串只有两种状态：aaa...a和aa...abb...b。所以:

  • dp[i][0]表示转化为aa...a的最少删除次数；
  • dp[i][1]表示转化为aa...abb...b的最少删除次数。
  • 如果s[i] == 'a'：
    • dp[i][0] = dp[i-1][0]
    • dp[i][1] = min(dp[i-1][0], dp[i-1][1]+1)
  • 如果s[i] == 'b'：
    • dp[i][0] = dp[i-1][0] + 1
    • dp[i][1] = min(dp[i-1][0], dp[i-1][1])

参考代码：

class Solution:
    def minimumDeletions(self, s: str) -> int:
        a, b = 0, 0
        for ch in s:
            if ch == 'a': a, b = a, min(a, b+1)
            else: a, b = a + 1, min(a, b)
        return min(a, b)

解法三：贪心

第一轮遍历计算'a'的数量，第二轮遍历判断在当前位置分割变为左边全为'a'右边全为'b'需要删除的字符数。

参考代码：

class Solution:
    def minimumDeletions(self, s: str) -> int:
        res, cnt = 0, 0
        for ch in s:
            if ch == 'a':
                cnt += 1
        res = cnt
        for ch in s:
            if ch == 'a': cnt -= 1
            else: cnt += 1
            res = min(res, cnt)
        return res

第二轮遍历相当于从0到len，假设在当前位置上分割，需要将左侧的'b'和右侧的'a'全部删除。在起始位置就是删除所有的'a'，每次向右滑动，如果当前位置是'a'，表示不需要删除这个'a'，因此-1；同理，如果当前位置是'b'，需要删除，则+1。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK