2017-07-02 170 views
2

我需要優化此代碼,基本上會檢查字符串s1的每個字符是否包含在s2中,同時考慮雙打。如何在Python中優化此代碼

s1, s2 = list(s1), list(s2) 
for s in s2: 
    if s in s1: 
     s1.remove(s) 
    else: 
     return False 
return True 

我做了map,迭代器和發電機一些研究,我敢肯定,在一個或一個以上的這些是有解決方案,但現在我很困惑和沮喪(我很新到python,僅僅幾個星期),所以也許你可以幫助我理解這種情況下最好的策略是什麼。謝謝!

+0

我不確定是否屬於這種情況。 's1.remove(s)'只是爲了避免重複字符的錯誤。例如,如果's1 ='aabcd'和's2 ='aaa''會返回'真',而它是假的。 list1 - list2如何幫助我?如果我有這個錯誤,請解釋我 – AndTuf

+1

目前尚不清楚你的預期輸出是什麼。請顯示[mcve]。 –

+0

不知道python中'in'的實現,這個代碼不會導致O(n^2)最壞的情況嗎? nlogn解決方案將排序並檢查它們是否相等。 –

回答

3

使用Counter一個解決方案,將正確處理重複的字符:

from collections import Counter 
c1 = Counter(s1) 
c2 = Counter(s2) 
return all(c2[c]>=c1[c] for c in c1) 
+1

你不想使用'> =',你只需要'=='。除此之外,很好的答案! –

+1

這是一個很好的,謝謝!不是'c2 [c]> = c1 [c]'但是'c1 [c]> = c2 [c]'但是,很好的回答 – AndTuf

+3

@NoticeMeSenpai如果s1和s2應該包含完全相同的字符,對,應該使用'=='。否則,我們可能會認爲沒有必要完全讀取s2,我們可以進一步優化(特別是如果s2比s1長得多)。 –

0

嗯......你可以繼續s1s2爲字符串,然後使用replace功能:

for c in s2: 
    if c in s1: 
     s1 = s1.replace(c, '', 1) 
    else: 
     return False 

return True 

str.replace(.., .., 1)刪除只有第一個出現該字符的。

+0

我不能使用'str.replace',因爲它會刪除所有的事件,而我需要正確處理重複的 – AndTuf

+0

@AndTuf編輯。 –

+0

噢,我的壞話,很高興知道 – AndTuf

1

你可以指望兩個字符串中的每個字符的出現次數。你也不需要使任何一個字符串成爲一個列表:字符串是他們自己的迭代器。

首先,創建set,因爲集合的平均查找次數爲O(1)。 然後,遍歷該集合並獲取每個字符的計數。如果有任何計數不相等,return False。它還擴展更好的爲字符串的大小增長,比當前解決方案:

s1 = 'Stack Overflow' 
s2 = 'woltk fcrSeavO' 

def equal_chars(s1, s2): 
    chars = set(s2) 
    for char in chars: 
     if s1.count(char)!= s2.count(char): 
      return False 
    return True 

print(equal_chars(s1, s2)) 
0

上阿德里安最偉大的回答略有調整是(也許?)更高效:

from collections import Counter 

s1 = "hello" 
s2 = "helo" 

def count_chars(s1,s2): 
    c2 = Counter(s2) 
    for k,v in Counter(s1).items(): 
     if c2[k] < v: 
      return False 
    return True 

print (count_chars(s1,s2)) 

結果:

False