数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python程序：统计字符串每个子串中不同字符的数量
假设我们有一个小写字符串 s，我们需要找到 s 的每个子串中不同字符数量的总和。如果答案非常大，则返回结果模 10^9+7。
因此，如果输入类似 s = "xxy"，则输出将为 6，因为子串及其计数为：
"x"：1
"x"：1
"y"：1
"xx"：0（因为 "x" 不唯一）
"xy"：2
"xxy"：1（因为 "x" 不唯一）
为了解决这个问题，我们将遵循以下步骤：
m := 10^9 + 7
prev_seen := 一个新的空映射
ans := 0
定义一个函数 util()。这将接收 i 和 symbol 作为参数。
prev_seen[symbol] := 一个包含单个值 -1 的列表
prev := prev_seen[symbol]
在 prev 的末尾插入 i
如果 prev 的大小 > 2，则
left := prev 的第一个元素，并从 prev 中删除第一个元素
middle := prev[0]，right := prev[1]
cnt := (middle - left) * (right - middle)
ans := (ans + cnt) mod m
对于 s 中的每个索引 i 和值 symbol，执行：
util(i, symbol)
对于 prev_seen 中的每个 symbol，执行：
util(s 的大小, symbol)
返回 ans
让我们看看下面的实现，以便更好地理解：
示例
class Solution:
def solve(self, s):
m = 10 ** 9 + 7
prev_seen = {}
ans = 0
def util(i, symbol):
nonlocal ans
prev = prev_seen.setdefault(symbol, [−1])
prev.append(i)
if len(prev) > 2:
left = prev.pop(0)
middle, right = prev
cnt = (middle − left) * (right − middle)
ans = (ans + cnt) % m
for i, symbol in enumerate(s):
util(i, symbol)
for symbol in prev_seen:
util(len(s), symbol)
return ans
ob = Solution()
s = "xxy"
print(ob.solve(s))输入
xxy
输出
6
更新于：2020-12-25
222 次浏览
广告