在 leetcode 上，這是被接受的，但提交失敗，因為它對于很長的字串來說太慢了。我在做什么太慢了，我應該加快速度？目標是在盡可能多地拆分字串時計算字串中的唯一字符數。
def numSplits(s):
good_splits = 0
string1 = ""
string2 = ""
repeated_chars_st1 = dict()
repeated_chars_st2 = dict()
for i in range(len(s)):
string1 = s[i]
string2 = s[i 1:]
for char in string1:
if char in repeated_chars_st1:
repeated_chars_st1[char] =1
else:
repeated_chars_st1[char] = 1
for char2 in string2:
if char2 in repeated_chars_st2:
repeated_chars_st2[char2] =1
else:
repeated_chars_st2[char2] = 1
left_counter = len(repeated_chars_st1.keys())
right_counter = len(repeated_chars_st2.keys())
if left_counter == right_counter:
good_splits =1
repeated_chars_st1.clear()
repeated_chars_st2.clear()
return good_splits
列印（numSplits（'aacaba'））
這是leetcode問題：
給你一個字串 s。
如果您可以將 s 拆分為兩個非空字串 sleft 和 sright，其中它們的串聯等于 s（即 sleft sright = s）并且 sleft 和 sright 中不同字母的數量相同，則拆分稱為好。
回傳您可以在 s 中進行的良好拆分的數量。
示例 1：
輸入：s = "aacaba" 輸出：2 解釋：拆分 "aacaba" 的方法有 5 種，其中 2 種是好的。("a", "acaba") 左字串和右字串分別包含 1 個和 3 個不同的字母。("aa", "caba") 左字串和右字串分別包含 1 和 3 個不同的字母。("aac", "aba") 左字串和右字串分別包含 2 個和 2 個不同的字母（很好的拆分）。("aaca", "ba") 左字串和右字串分別包含 2 個和 2 個不同的字母（很好拆分）。("aacab", "a") 左字串和右字串分別包含 3 個和 1 個不同的字母。示例 2：
輸入：s = "abcd" 輸出：1 解釋：按如下方式拆分字串（“ab”，“cd”）。
約束：
1 <= s.length <= 105 s 僅由小寫英文字母組成。
uj5u.com熱心網友回復：
通過對問題的描述，您不需要使解決方案如此復雜。你能試試這個，它應該作業。
def sol(s):
count = 0
for i in range(1,len(s)):
s_left = s[0:i]
s_right = s[i:]
l = len(set(s_left))
r = len(set(s_right))
if l==r:
count =1
return count
print(sol('aacaba'))
uj5u.com熱心網友回復：
如果更有效的話，可能是 Ritwick 以前的答案，但是如果你想學習一些東西，你可以看到如果你重用上一次迭代中的字典，你應該會獲得很多性能。如果您對此進行分析，則字典在相鄰拆分中非常相似，實際上，字典是相同的，它只是將一個字符從字典“移動”到另一個字符。
使用上述陳述句，另一種可能的解決方案是
def numSplits(s):
good_splits = 0
repeated_chars_st1 = dict()
repeated_chars_st2 = dict()
# Put everything in dict1
for char in s:
if char in repeated_chars_st1:
repeated_chars_st1[char] =1
else:
repeated_chars_st1[char] = 1
for i in range(len(s)):
# Move the current character
char = s[i]
repeated_chars_st1[char] -= 1
if char in repeated_chars_st2:
repeated_chars_st2[char] =1
else:
repeated_chars_st2[char] = 1
# Check good split as before
left_counter = len(repeated_chars_st1.keys())
right_counter = len(repeated_chars_st2.keys())
if left_counter == right_counter:
good_splits =1
return good_splits
uj5u.com熱心網友回復：
兩個問題：
- 您實際上是將兩個子字串分配給變數。這是不必要的復制。
- 將 char 從 string2 移動到 string1 后，重新計算兩個字串中的所有字符。
為了足夠快，您需要有兩個哈希圖來計算 string1 和 string2 中的字符數。每次迭代，您傳輸一個字符并僅修改它的兩個計數器。如果計數器達到零或變為非零，則您將擁有新數量的不同字符。每當兩個計數器中不同字符的數量相等時，將結果加一并最終回傳結果。
這段代碼應該清楚
class Solution:
def numSplits(self, s: str) -> int:
counter1 = {}
counter2 = {}
for c in s:
if c not in counter2:
counter2[c] = 0
counter2[c] = 1
distinct1 = 0
distinct2 = len(counter2.keys())
result = 0
for i in range(len(s)):
c = s[i]
if distinct1 == distinct2:
result = 1
# add c to string1
if c not in counter1:
distinct1 = 1
counter1[c] = 0
counter1[c] = 1
# remove c from string2
counter2[c] -= 1
if counter2[c] == 0:
distinct2 -= 1
del counter2[c]
return result
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/497557.html