LeetCode 1422. 分割字符串的最大得分

1422. 分割字符串的最大得分

题目：给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个 非空 子字符串（即 左 子字符串和 右 子字符串）所能获得的最大得分。
「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。

链接 https://leetcode.cn/problems/maximum-score-after-splitting-a-string/

个人思路

1. 没想到别的好方法，只能先统计从s[0]位置开始切割时能获得多少分score，然后再向右移动，遇到1时减1分，遇到0时加1分，并且记录在这之间获得的最大分数。

class Solution:
    def maxScore(self, s: str) -> int:
        score = 1 if s[0] == '0' else 0
        score += s[1:].count('1')
        maxS = score
        for i in s[1:len(s)-1]:
            if i == '0':
                score += 1
                if score > maxS:
                    maxS = score
            else:
                score -= 1
        return maxS
1
2
3
4
5
6
7
8
9
10
11
12
13

官方写法：

class Solution:
    def maxScore(self, s: str) -> int:
        ans = score = (s[0] == '0') + s[1:].count('1')
        for c in s[1:-1]:
            score += 1 if c == '0' else -1
            ans = max(ans, score)
        return ans
1
2
3
4
5
6
7

官方用时比我的慢，我的有时能超越100%，可能是它score不管是＋1还是－1都要和ans比较的原因

复杂度分析
时间复杂度：O(n)，其中 n 是字符串 s 的长度。需要遍历字符串两次。
空间复杂度：O(1)。

2. 枚举每个分割点
   遍历所有的分割点，即可得到分割字符串的最大得分。

class Solution:
    def maxScore(self, s: str) -> int:
        return max(s[:i].count('0') + s[i:].count('1') for i in range(1, len(s)))
1
2
3

复杂度分析

时间复杂度：O(n ^ 2)，其中 n 是字符串 s 的长度。需要遍历 n - 1个分割点，对于每个分割点需要 O(n) 的时间遍历整个字符串计算分割字符串的得分，因此时间复杂度是 O(n ^ 2)。
空间复杂度：O(1)。

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/maximum-score-after-splitting-a-string/solution/fen-ge-zi-fu-chuan-de-zui-da-de-fen-by-l-7u5p/