頻度表で文字を数える
dict または配列で文字の出現回数を集計します
「頻度表で文字を数える」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
文字を数える理由
文字列問題の多くは、「各文字が何回現れるか」という1つの問いに行き着きます。頻度表を使えば、1回の走査で答えを求められます。📊
辞書を使う方法
通常のdictで、各文字をその出現回数に対応付けます。Unicodeや記号を含む、どのような文字集合にも対応できます。
freq = {}
for ch in 'apple':
freq[ch] = freq.get(ch, 0) + 1
print(freq)get()でKeyErrorを回避する
get(ch, 0)を使うと、キーが存在しない場合に0が返されます。そのため、文字を初めて見たときもスムーズに1から数え始められます。
Counterに任せる
collectionsのCounterクラスを使えば、表全体を1行で作成できます。速度と分かりやすさを両立できる、競技プログラミングの定番です。
from collections import Counter
freq = Counter('apple')
print(freq['p']) # 2存在しないキーは0を返す
Counterは存在しないキーに対してエラーを発生させません。一度も見ていない文字を尋ねると0が返るため、分岐のないコードを書けます。
from collections import Counter
c = Counter('abc')
print(c['z']) # 0固定長配列を使う方法
小文字だけを扱うなら、26要素のリストがさらに高速です。ordを使った計算で各文字をインデックス化し、カウントを増やします。
cnt = [0] * 26
for ch in 'apple':
cnt[ord(ch) - ord('a')] += 1配列とdictの使い分け
配列は最も高速ですが、既知の小さな文字集合にしか適しません。dictやCounterなら、わずかなコストで任意の文字に対応できます。
最頻出の文字を見つける
Counterのmost_common(k)を使うと、頻度順に並べ替えられた上位k個の文字が返されます。手動でソートする必要はありません。
from collections import Counter
print(Counter('mississippi').most_common(1))2つの表を比較する
2つの文字列は、頻度表が一致するとき、かつそのときに限りアナグラムです。2つのCounterを比較すれば1行で判定できます。
from collections import Counter
print(Counter('listen') == Counter('silent')) # True1回の走査で十分
表の構築は文字列を1回走査するO(n)の処理です。その後の各検索は定数時間で行えます。
引き算で余分な文字を見つける
Counterは引き算に対応しているため、一方の文字列にあって他方にない文字を見つけられます。身代金メモ型の問題に便利です。
from collections import Counter
print(Counter('aabb') - Counter('ab'))クイックチェック
文字のカウントについて、1問確認しましょう。
まとめ
これで、dict、Counter、または26要素の配列を使って文字を集計し、その表でアナグラムの判定や頻出文字の検索ができるようになりました。🎉
よくある質問
「頻度表で文字を数える」レッスンは無料ですか？
はい。「頻度表で文字を数える」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「頻度表で文字を数える」で何を学びますか？
dict または配列で文字の出現回数を集計します ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「頻度表で文字を数える」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。