這個Python Dict代碼爲什麼工作？

-1

def isPerm(s1, s2): 
    if len(s1) != len(s2): 
     return False 
    a = dict() 
    for char in s1: 
     a[char] = True 
    for char2 in s2: 
     if a.get(char2) == True: 
      continue 
     else: return False 
    return True

這是我寫的函數，用來查找兩個字符串是否相互排列。但我不知道爲什麼這個工程（我得到正確的輸出），當我通過它的理由。據我所知，字典就像一個哈希表。這個Python Dict代碼爲什麼工作？

例如，如果我有s1和s2作爲「ab」和「aab」，這應該給我False，這個函數的作用。現在，在第一個for循環中，當我訪問s1中的每個char時，我有一個帶有「a」和「b」映射爲True的字典。

當我去第二個循環，我檢查「a」的字典值，它是真的，所以我繼續。在第二個角色中，我再次得到一個「a」，這是真實的，在第三次迭代中，「b」也給了我真實的答案。所以，函數應該給我真實的，但它給了我錯誤。我很困惑，爲什麼它的工作！

來源

2014-10-01 addybist

想想'如果len（S1）= LEN（S2）：' – thefourtheye 2014-10-01 05:19:28

我認爲這將失敗，'isPerm（ 'AAB'， 'ABB'）' – inspectorG4dget 2014-10-01 05:20:23

您的程序工作正常，因爲它返回False，因爲函數中檢查到了第一個條件。

if len(s1) != len(s2): 
    return False

由於ab和aab大小不同，它會立即失敗。

但是，作爲inspectorG4dget points out，您的程序將失敗的輸入aab和abb。

要真正發現一個字符串是否是另一個字符串的置換，應該計算每個字符在兩個字符串中出現的次數，並且如果所有計數相等，則返回True。這可以在Python做與collections.Counter的幫助下，像這樣的

from collections import Counter 
def isPerm(s1, s2): 
    return Counter(s1) == Counter(s2)

的collections.Counter讓你的人物和他們對應的計數的字典。例如，

>>> from collections import Counter 
>>> Counter("aab") 
Counter({'a': 2, 'b': 1}) 
>>> Counter("abb") 
Counter({'b': 2, 'a': 1}) 
>>> Counter("aab") == Counter("abb") 
False 
>>> Counter("aab") == Counter("aba") 
True

只有普通的字典的另一種方法，

def counter(s): 
    d = {} 
    for char in s: 
     d[char] = d.get(char, 0) + 1 
    return d 

def isPerm(s1, s2): 
    return counter(s1) == counter(s2) 

assert isPerm("aab", "aba") == True 
assert isPerm("aab", "abb") == False

來源

2014-10-01 05:22:25 thefourtheye

哦，這完全是有道理的。謝謝！一個簡單的問題 - 櫃檯的運行時間是多少？如果它是O（n），那麼這個算法將是O（n^2）。這兩個列表不會更好，因爲那會是O（nlogn）？ – addybist 2014-10-01 05:41:30

@AdityaBist它是如何O（N^2）？你正在做兩次O（N）操作。所以它仍然只是O（N）:) – thefourtheye 2014-10-01 05:44:11

不，@AdityaBist，它不是O（n^2），它只是O（n），因爲計數器是相互獨立創建的，並且計數器的比較也是O（n）。 – 2014-10-01 05:44:28

代碼溶液檢查置換是簡單得多。它也是O(nlogn)的複雜性。只需排序字符串並比較結果。

def isPerm(s1, s2): 
    return sorted(s1) == sorted(s2)

來源

2014-10-01 06:49:50

這個Python Dict代碼爲什麼工作？

回答

相關問題