3707. 相等子字符串分数

题目描述

给你一个由小写英文字母组成的字符串 s。

一个字符串的得分是其字符在字母表中的位置之和，其中 'a' = 1，'b' = 2，...，'z' = 26。

请你判断是否存在一个下标 i，使得该字符串可以被拆分成两个 非空子字符串 s[0..i] 和 s[(i + 1)..(n - 1)]，且它们的得分相等。

如果存在这样的拆分，则返回 true，否则返回 false。

一个 子字符串 是字符串中非空的连续字符序列。

示例 1:

输入: s = "adcb"

输出: true

解释:

在下标 i = 1 处拆分：

左子字符串 = s[0..1] = "ad"，得分 = 1 + 4 = 5
右子字符串 = s[2..3] = "cb"，得分 = 3 + 2 = 5

两个子字符串的得分相等，因此输出为 true。

示例 2:

输入: s = "bace"

输出: false

解释:

没有拆分能产生相等的得分，因此输出为 false。

提示:

2 <= s.length <= 100
s 由小写英文字母组成。

解法

方法一：前缀和

我们先计算字符串的总得分，记为 \(r\)。然后我们从左到右遍历前 \(n-1\) 个字符，计算前缀得分 \(l\)，并更新后缀得分 \(r\)。如果在某个位置 \(i\)，前缀得分 \(l\) 等于后缀得分 \(r\)，则说明存在一个下标 \(i\) 可以将字符串拆分成两个得分相等的子字符串，返回 \(\textit{true}\)。如果遍历结束后仍未找到这样的下标，返回 \(\textit{false}\)。

时间复杂度 \(O(n)\)，其中 \(n\) 是字符串的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def scoreBalance(self, s: str) -> bool:
        l = 0
        r = sum(ord(c) - ord("a") + 1 for c in s)
        for c in s[:-1]:
            x = ord(c) - ord("a") + 1
            l += x
            r -= x
            if l == r:
                return True
        return False

class Solution {
    public boolean scoreBalance(String s) {
        int n = s.length();
        int l = 0, r = 0;
        for (int i = 0; i < n; ++i) {
            int x = s.charAt(i) - 'a' + 1;
            r += x;
        }
        for (int i = 0; i < n - 1; ++i) {
            int x = s.charAt(i) - 'a' + 1;
            l += x;
            r -= x;
            if (l == r) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
public:
    bool scoreBalance(string s) {
        int l = 0, r = 0;
        for (char c : s) {
            int x = c - 'a' + 1;
            r += x;
        }
        for (int i = 0; i < s.size() - 1; ++i) {
            int x = s[i] - 'a' + 1;
            l += x;
            r -= x;
            if (l == r) {
                return true;
            }
        }
        return false;
    }
};

func scoreBalance(s string) bool {
    var l, r int
    for _, c := range s {
        x := int(c-'a') + 1
        r += x
    }
    for _, c := range s[:len(s)-1] {
        x := int(c-'a') + 1
        l += x
        r -= x
        if l == r {
            return true
        }
    }
    return false
}

function scoreBalance(s: string): boolean {
    let [l, r] = [0, 0];
    for (const c of s) {
        const x = c.charCodeAt(0) - 96;
        r += x;
    }
    for (let i = 0; i < s.length - 1; ++i) {
        const x = s[i].charCodeAt(0) - 96;
        l += x;
        r -= x;
        if (l === r) {
            return true;
        }
    }
    return false;
}

3707. 相等子字符串分数

题目描述

解法

方法一：前缀和

评论