資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢最大數量的無重疊子串
假設我們有一個僅包含小寫字母的字串 s，我們需要找到 s 的最大數量的非空子串，這些子串滿足以下規則：
子串不重疊。
包含特定字元 ch 的子串必須包含 ch 的所有出現。
我們需要找到滿足這兩個條件的最大子串數量。如果有多個子串數量相同的解，則返回總長度最小的解。
例如，如果輸入為 s = "pqstpqqprrr"，則輸出為 ["s","t","rrr"]，因為滿足條件的所有可能的子串為 ["pqstpqqprrr", "pqstpqqp", "st", "s", "t", "rrr"]
為了解決這個問題，我們將遵循以下步驟：
right := 對 s 中所有單個字元 ch 的索引位置從右向左排序。
left := 對所有 i ∈ right 的字元 s[i] 的索引列表。
has := 空列表，gen := 空列表。
對於 i 從 0 到 right 的大小 - 1：
將來自 s[right[i]] 的新字元集插入 gen 的末尾。
將來自 s[從索引 (left[i] + 1 到 right[i]-1) - gen 的最後一項] 的子串的新字元集插入 has 的末尾。
對於 j 從 has 的大小 - 2 到 0：
如果 (has 的最後一項 AND gen[j]) 且 (has[j] AND gen 的最後一項) 不為零，則：
gen 的最後一項 := gen 的最後一項 OR gen[j]
has 的最後一項 := (has 的最後一項 OR has[j]) - gen 的最後一項
移除 has[j]，gen[j]
res := 新列表，p_right := -1
對於 ind 從 0 到 has 的大小 - 1：
l := 如果 s[i] 出現在 gen[ind] 中，則所有 i ∈ left 的元素 i 的最小值。
r := 如果 s[i] 出現在 gen[ind] 中，則所有 i ∈ right 的元素 i 的最大值。
如果 p_right < l，則：
將 s[從索引 l 到 r] 的子串插入 res 的末尾。
p_right := r
返回 res
示例
讓我們看下面的實現來更好地理解。
def solve(s):
right = sorted([s.rindex(ch) for ch in set(s)])
left = [s.index(s[i]) for i in right]
has, gen = [], []
for i in range(len(right)):
gen.append(set(s[right[i]]))
has.append(set(s[left[i] + 1:right[i]]) - gen[-1])
for j in range(len(has) - 2, -1, -1):
if (has[-1] & gen[j]) and (has[j] & gen[-1]):
gen[-1] = gen[-1] | gen[j]
has[-1] = (has[-1] | has[j]) - gen[-1]
del has[j], gen[j]
res, p_right = [], -1
for ind in range(len(has)):
l = min([i for i in left if s[i] in gen[ind]])
r = max([i for i in right if s[i] in gen[ind]])
if p_right < l:
res.append(s[l : r + 1])
p_right = r
return res
s = "pqstpqqprrr"
print(solve(s))輸入
"pqstpqqprrr"
輸出
['s', 't', 'rrr']
562 次瀏覽
