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 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告