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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告