Easy

题目描述

给你一个由小写英文字母组成的字符串 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 由小写英文字母组成

提示：

  • 使用暴力方法

解题思路

解题思路

这道题要求我们找到一个分割点，使得左右两部分的分数相等。由于字符串长度最多100，我们可以使用暴力方法来解决。

基本思路：

  1. 遍历所有可能的分割点 i（从0到n-2，确保两部分都非空）
  2. 对于每个分割点，分别计算左子串和右子串的分数
  3. 如果找到分数相等的分割，返回 true

优化思路： 可以使用前缀和来优化计算：

  1. 首先计算整个字符串的总分数
  2. 遍历分割点时，维护左子串的分数，右子串分数 = 总分数 - 左子串分数
  3. 当左右分数相等时返回 true

字符分数计算： 对于字符 c，其分数为 c - 'a' + 1

时间复杂度为 O(n)，空间复杂度为 O(1)，这种方法既简单又高效。

代码实现

class Solution {
public:
    bool scoreBalance(string s) {
        int n = s.length();
        
        // 计算总分数
        int totalScore = 0;
        for (char c : s) {
            totalScore += c - 'a' + 1;
        }
        
        int leftScore = 0;
        
        // 遍历所有可能的分割点
        for (int i = 0; i < n - 1; i++) {
            leftScore += s[i] - 'a' + 1;
            int rightScore = totalScore - leftScore;
            
            if (leftScore == rightScore) {
                return true;
            }
        }
        
        return false;
    }
};

class Solution:
    def scoreBalance(self, s: str) -> bool:
        n = len(s)
        
        # 计算总分数
        total_score = sum(ord(c) - ord('a') + 1 for c in s)
        
        left_score = 0
        
        # 遍历所有可能的分割点
        for i in range(n - 1):
            left_score += ord(s[i]) - ord('a') + 1
            right_score = total_score - left_score
            
            if left_score == right_score:
                return True
        
        return False

public class Solution {
    public bool ScoreBalance(string s) {
        int n = s.Length;
        
        // 计算总分数
        int totalScore = 0;
        foreach (char c in s) {
            totalScore += c - 'a' + 1;
        }
        
        int leftScore = 0;
        
        // 遍历所有可能的分割点
        for (int i = 0; i < n - 1; i++) {
            leftScore += s[i] - 'a' + 1;
            int rightScore = totalScore - leftScore;
            
            if (leftScore == rightScore) {
                return true;
            }
        }
        
        return false;
    }
}

/**
 * @param {string} s
 * @return {boolean}
 */
var scoreBalance = function(s) {
    const n = s.length;
    
    for (let i = 0; i < n - 1; i++) {
        let leftScore = 0;
        let rightScore = 0;
        
        for (let j = 0; j <= i; j++) {
            leftScore += s.charCodeAt(j) - 96;
        }
        
        for (let j = i + 1; j < n; j++) {
            rightScore += s.charCodeAt(j) - 96;
        }
        
        if (leftScore === rightScore) {
            return true;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(n)，其中 n 是字符串长度。需要遍历一次字符串计算总分数，然后遍历 n-1 个分割点
空间复杂度O(1)，只使用了常数个变量来存储分数