Medium

题目描述

给你一个字符串 s。

我们定义英文字母表中字母的镜像为字母表反转后对应的字母。例如，'a' 的镜像是 'z'，'y' 的镜像是 'b'。

最初，字符串 s 中的所有字符都是未标记的。

你从分数 0 开始，对字符串 s 执行以下过程：

  • 从左到右遍历字符串。
  • 对于每个索引 i，找到最近的未标记索引 j，使得 j < i 且 s[j] 是 s[i] 的镜像。然后，标记索引 i 和 j，并将值 i - j 添加到总分数中。
  • 如果对于索引 i 不存在这样的索引 j，则继续下一个索引而不做任何改变。

返回过程结束时的总分数。

示例 1：

输入：s = "aczzx"
输出：5
解释：
- i = 0. 没有满足条件的索引 j，跳过。
- i = 1. 没有满足条件的索引 j，跳过。
- i = 2. 满足条件的最近索引 j 是 j = 0，标记索引 0 和 2，然后将 2 - 0 = 2 添加到分数中。
- i = 3. 没有满足条件的索引 j，跳过。
- i = 4. 满足条件的最近索引 j 是 j = 1，标记索引 1 和 4，然后将 4 - 1 = 3 添加到分数中。

示例 2：

输入：s = "abcdef"
输出：0
解释：
对于每个索引 i，都没有满足条件的索引 j。

约束条件：

  • 1 <= s.length <= 10^5
  • s 仅由小写英文字母组成。

提示：

  • 为每个字符创建一个栈。
  • 对于每个索引，检查该索引处字母的镜像对应的栈是否为空。

解题思路

这道题的关键在于理解"镜像字母"的定义和"最近的未标记索引"的含义。

思路分析：

  1. 镜像字母映射：对于字母 c，其镜像为 'a' + 'z' - c。例如 'a' 的镜像是 'z'，'b' 的镜像是 'y'。

  2. 栈数据结构：由于我们需要找到"最近的"未标记索引，这意味着要找到距离当前位置最近的匹配字符。使用栈可以很好地维护每个字符出现的位置，栈顶总是最近的位置。

  3. 算法流程：

    • 为每个字母（26个）维护一个栈，存储该字母出现的未标记位置
    • 从左到右遍历字符串
    • 对于位置 i 的字符，查找其镜像字符对应的栈
    • 如果镜像字符的栈非空，取出栈顶位置 j，计算 i - j 加入答案
    • 如果镜像字符的栈为空，将当前位置 i 压入当前字符对应的栈

这种方法的优势是能够高效地找到最近的匹配位置，时间复杂度为 O(n)。

代码实现

class Solution {
public:
    long long calculateScore(string s) {
        vector<stack<int>> stacks(26);
        long long score = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s[i];
            char mirror = 'a' + 'z' - c;
            int mirrorIdx = mirror - 'a';
            
            if (!stacks[mirrorIdx].empty()) {
                int j = stacks[mirrorIdx].top();
                stacks[mirrorIdx].pop();
                score += i - j;
            } else {
                stacks[c - 'a'].push(i);
            }
        }
        
        return score;
    }
};

class Solution:
    def calculateScore(self, s: str) -> int:
        stacks = [[] for _ in range(26)]
        score = 0
        
        for i, c in enumerate(s):
            mirror = chr(ord('a') + ord('z') - ord(c))
            mirror_idx = ord(mirror) - ord('a')
            
            if stacks[mirror_idx]:
                j = stacks[mirror_idx].pop()
                score += i - j
            else:
                stacks[ord(c) - ord('a')].append(i)
        
        return score

public class Solution {
    public long CalculateScore(string s) {
        Stack<int>[] stacks = new Stack<int>[26];
        for (int i = 0; i < 26; i++) {
            stacks[i] = new Stack<int>();
        }
        
        long score = 0;
        
        for (int i = 0; i < s.Length; i++) {
            char c = s[i];
            char mirror = (char)('a' + 'z' - c);
            int mirrorIdx = mirror - 'a';
            
            if (stacks[mirrorIdx].Count > 0) {
                int j = stacks[mirrorIdx].Pop();
                score += i - j;
            } else {
                stacks[c - 'a'].Push(i);
            }
        }
        
        return score;
    }
}

var calculateScore = function(s) {
    const stacks = Array(26).fill().map(() => []);
    let score = 0;
    
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        const mirror = String.fromCharCode('a'.charCodeAt(0) + 'z'.charCodeAt(0) - c.charCodeAt(0));
        const mirrorIdx = mirror.charCodeAt(0) - 'a'.charCodeAt(0);
        
        if (stacks[mirrorIdx].length > 0) {
            const j = stacks[mirrorIdx].pop();
            score += i - j;
        } else {
            stacks[c.charCodeAt(0) - 'a'.charCodeAt(0)].push(i);
        }
    }
    
    return score;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

说明：

  • 时间复杂度：遍历字符串一次，每个字符最多入栈和出栈各一次，总体为 O(n)
  • 空间复杂度：最坏情况下所有字符都需要存储在栈中，为 O(n)