数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：计算同质子字符串的数量
假设我们有一个字符串 s，我们需要找到 s 的同质子字符串的数量。答案可能非常大，因此返回答案模 10^9+7。当字符串的所有字符都相同的时候，该字符串被称为同质字符串。
因此，如果输入像 s = "xyyzzzxx"，则输出将是 13，因为同质子字符串列出如下：
1."x" 出现三次。
"xx" 出现一次。
3. "y" 出现两次。
"yy" 出现一次。
5. "z" 出现三次。
"zz" 出现两次。
"zzz" 出现一次。
所以，(3 + 1 + 2 + 1 + 3 + 2 + 1) = 13。
为了解决这个问题，我们将遵循以下步骤：
s := s 连接 "@"
h:= 一个新的映射
prev:= s[0]
c:= 1
对于 s 中从索引 1 到末尾的每个 i，执行以下操作：
如果 prev 与 i 不相同，则
如果 prev*c 存在于 h 中，则
h[prev*c] := h[prev*c] + 1
否则，
h[prev*c]:= 1
c:= 1
如果 prev 与 i 相同，则
c := c + 1
prev := i
fin:= 0
对于 h 中的每个 i，执行以下操作：
t:= i 的大小
k:= 0
当 t 与 0 不相同时，执行以下操作：
k := k + t
t := t - 1
fin := fin + k*h[i]
返回 fin 模 10^9+7
示例
让我们看看以下实现，以便更好地理解：
def solve(s):
s+="@"
h={}
prev=s[0]
c=1
for i in s[1:]:
if prev!=i:
if prev*c in h:
h[prev*c]+=1
else:
h[prev*c]=1
c=1
if prev == i:
c += 1
prev = i
fin=0
for i in h:
t=len(i)
k=0
while t!=0:
k+=t
t-=1
fin+=k*h[i]
return fin % 1000000007
s = "xyyzzzxx"
print(solve(s))输入
"xyyzzzxx"
输出
13
更新于: 2021年10月6日
339 次浏览
广告