题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个字符串，和一个叫镜像的概念。’a’的镜像是’z’，’b’的镜像是’y’以此类推。现在要从左向右遍历字符串，当遇到没有标记的字符时，找前面没有标记字符中的镜像，如果存在，则累积下标差为分数。

思路分享

  • 由于字符需要与遍历过的字符交互，所以涉及到了枚举的技巧，也就是通过数据结构记录遍历的数据，本题就是用字典（哈希表）来记录已经遍历的 26 字母的情况，然后就能 O(1) 复杂度计算分数。

  • 由于取之前的字母要求是最近的，所以就用栈来管理各个字母的下标，栈顶就是最近的，这样每次计算完直接 pop 掉也方便。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def calculateScore(self, s: str) -> int:
        rec = defaultdict(list)
        mirror = defaultdict(str)
        i, j = ord('a'), ord('z')
        while i < j:
            mirror[chr(i)] = chr(j)
            mirror[chr(j)] = chr(i)
            i += 1
            j -= 1

        ans = 0
        for i, c in enumerate(s):
            if rec[mirror[c]]:
                ans += i-rec[mirror[c]].pop()
            else:
                rec[c].append(i)

        return ans