資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告