對不起，如果標題不準確，但我不確定如何命名，因為我是一個菜鳥。
我正在嘗試解決一個挑戰：
“完成的功能scramble(str1, str2)即回傳True如果的一部分s1字符可以被重新排列以匹配s2，否則回傳False。 ”
所以首先我想像這樣完成它：
return True if "".join(str(e) for e in s2 if e in s1 and s1.count(e) >= s2.count(e)) == s2 else False
但是，這會超時并且顯然沒有得到充分優化。
我不以為然，我認為它與該count()方法有關，所以我試圖e從s1下面洗掉if ein s1- 因為當s2在s1其中找到一個字符時，它不能再次使用（除非s1.因此，例如s2 = 'stress'需要 3 次's' 出現s1才能使函式回傳True。
然而，在下面的代碼中，它看起來像這部分：s1.replace(e, '', 1)在我之前/之后列印時不做任何事情。
def scramble(s1, s2):
print(s1)
("".join(str(e), s1.replace(e, '', 1)) for e in s2 if e in s1)
print(s1)
scramble('abcdefghijklmnopqrstuvzxy', 'stress')
我能做什么？
uj5u.com熱心網友回復：
您的演算法會遍歷 中的每個字符s2，然后為s1和找到該字符的字符數s2。為便于記號，請使用 letm = len(s1)和n = len(s2)。然后，每個.count()操作在呼叫 的字串中的字符數上花費線性時間.count()。所以，我們有O(n)迭代，并且O(m n)每次迭代都作業——我們的最終運行時是O(n*m n^2). 如果s2真的很長，我們將看到很多放緩。
通過在開始分析之前生成計數，我們可以做得更好。
# You can use collections.Counter() here, but I've chosen to forgo this to make the runtime analysis clearer.
def count_characters(s):
chars = {}
for char in s:
if char in chars:
chars[char] = 1
else:
chars[char] = 1
return chars
def scramble2(s1, s2):
s1_characters = count_characters(s1)
s2_characters = count_characters(s2)
for char in s2_characters:
if char not in s1_characters or s1_characters[char] < s2_characters[char]:
return False
return True
我們來分析修改后的演算法的運行時間：
count_characters()與輸入字串的長度成線性關系。所以字符計數器需要O(m n)時間來生成。然后，我們需要檢查 中的每個計數器s2_characters，并將其與 中的計數器進行比較s1_characters。無論您是否假設字母表大小不變，O(n)在最壞的情況下這都需要時間。所以，最終的運行時間是O(m n)——即輸入字串的長度是線性的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/402192.html