0
私はhackerrankを試していましたが、私はpython3を使って解決しようとした問題に出くわしました。 問題があった "誘拐犯が身代金を書いたが、彼が追跡されることを心配している。彼は雑誌を見つけて、彼がそれからすべての言葉を切り捨てて、身代金は大文字と小文字が区別され、雑誌で利用可能な全単語を使用する必要があります。つまり、部分文字列や連結を使用して必要な単語を作成することはできません。1つの方法が別の方法より効率的な理由は何ですか？
雑誌の単語と単語身代金の欄には、マガジンからの言葉全体を正確に使って身代金を複製できる場合は「はい」を、それ以外の場合は「いいえ」を、
私はこれが仕事をした
def ransom_note(magazine, ransom):
# comparing based on the number of times word occurred in the list
for word in set(ransom):
if ransom.count(word) > magazine.count(word):
return False
return True
、次のアプローチを使用してみました、私は右の20のテストケースのうち、18を得ました。 しかし、他の2つのケースがタイムアウトしていたので、私はこれを行う最もコスト効率のよい方法を得なければなりませんでした。 私は単語をキーとして単語の値を値として使用して単語を辞書として保存しようとしました。まだ2つのケースを得ていないのですが、入力と出力の両方に30000ワードがあるケースを見てみると、「はい」でした。
私はこのディスカッションのページを見て、私に手を差し伸べるコードを見つけました。
from collections import Counter
def ransom_note(magazine, ransom):
return not (Counter(ransom) - Counter(magazine))
私の方法よりも効率が良い理由を説明できる人はいますか？事前に 感謝:)
なぜそれを一度やって参照するのと比べて何度も何度も何度も何度も何度も何度も何度もやり取りするのですか？辞書を持ってそれを一度格納するのと比べて 'for'ループに' transom.count（word） 'と' magazine.count'を追加しました。 – shahkalpesh
あなたのアプローチは素朴な 'O（N^2）'アルゴリズムですが、Counterクラスはマルチセットを使ってカウントプロセスを最適化します – PythEch