假設有兩個字串陣列。一個陣列命名為查詢，另一個命名為字典。對于查詢的每個字串元素，您需要找出它在字典元素中存在多少字謎，并將該數字推送到另一個陣列。您的代碼必須回傳該陣列，并且它的大小應該等于查詢的大小（如預期的那樣）。
我解決這個問題的方法是：
- 遍歷查詢和字典的每個元素（在嵌套回圈中）；
- 檢查查詢元素的長度是否等于字典的嵌套元素。如果是，那么我使用
set(word)==set(st)（st 指的是字典）檢查了它們是否具有相同的字符。
我的代碼是這樣的：
anagrams = list()
for word in query:
ana = 0
for st in dictionary:
if(len(word)==len(st)):
if(set(word)==set(st)):
ana = ana 1
anagrams.append(ana)
這個邏輯給了我正確的結果，但沒有優化。結果，它超過了 10 秒的時間限制。查詢和字典的長度都可以達到 10^15。
我的邏輯在 O(n^2) 時間內運行。有什么辦法可以進一步優化代碼嗎？
uj5u.com熱心網友回復：
您可以使用 Pythondict離子來加快速度：
dict_sorted = {}
for s in dictionary: # linear in terms of the size of `dictionary`
sorted_s = sorted(s.lower())
dict_sorted[sorted_s] = dict_sorted.get(sorted_s, 0) 1
anagrams = []
for s in query: # linear in terms of the size of `query`
sorted_s = sorted(s.lower())
anagrams.append(dict_sorted.get(sorted_s, 0))
用于collections.Counter縮短事物：
from collections import Counter
dict_sorted = Counter([sorted(s.lower()) for s in dictionary])
anagrams = [ dict_sorted.get(sorted(s.lower()), 0) for s in query ]
uj5u.com熱心網友回復：
如果您測驗字符集和長度，您的邏輯是不正確的，abbc并且aabc看起來像是字謎，它們不是。
現在有一個 O(n) 時間，您可以使用 計算字典中每個單詞中的字符collections.Counter，并轉換為專案，然后將 freezeset 本身在計數器中散列。然后只需檢查查詢的每個單詞一次：
from collections import Counter
query = ['aabc', 'xyz', 'opq']
dictionary = ['abac', 'baac', 'xyz', 'jkl', 'yxz']
c = Counter(frozenset(Counter(w).items()) for w in dictionary)
anagrams = [c[frozenset(Counter(w).items())] for w in query]
輸出： [2, 2, 0]
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/418890.html
標籤：