Count a Character
文字列 s と1文字の c が与えられます。s に c が何回出現するかを返してください。大文字と小文字は区別されます。B と b は異なる文字なので、c と完全に一致するものだけを数えます。
関数
- sstring
- 検索する英字の文字列
- cstring
- 数える文字
- 戻り値integer
- s のうち c と等しい文字の数
制約
1 ≤ s.length ≤ 5 × 104sには英字（aからz、AからZ）のみが含まれます。cは英字ちょうど1文字です。
例
- 入力
- s = "Mississippi"c = "s"
- 出力
- 4
- 説明
Mississippiには、0から数えて位置2、3、5、6にsがあるため、答えは4です。
- 入力
- s = "Banana"c = "b"
- 出力
- 0
- 説明
Bananaは大文字のBで始まりますが、検索対象は小文字のbです。2つは異なるため、何も一致せず、答えは0です。
提出時に隠しテスト+18件
発展問題
もしcがssのように複数の文字からなる単語だったらどうでしょうか？重なり合う一致も数えますか？また、ループはどのように変わりますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
cが何回出現するかを知るには、sのどの文字を調べる必要がありますか？sの各文字を、cとそのまま比較します。ここでは、大文字と小文字は異なる文字です。0から始まるカウンターを用意します。文字列を一度走査し、現在の文字が
cと等しいときに1を加算します。
解説
sのすべての文字を一度ずつ確認する必要があります。どの文字もcである可能性があるためです。カウンターを使って1回走査します。つまずきやすい点は、大文字と小文字（大文字は別の文字です）と、言語によっては文字を1文字の文字列と比較することです。
すべての c を削除して、長さを比較する
考え方
sからcをすべて取り除いたコピーを作ります。取り除いた文字ごとにコピーは1文字短くなるため、2つの長さの差は、cが現れた回数とちょうど一致します。ほとんどの言語には、削除を行うreplace関数またはdelete関数があります。
Mississippiとsの場合、コピーはMiiippiです。元の11文字に対して7文字なので、cは4回現れました。Bananaとbの場合、大文字のBは一致しないため何も削除されず、差は0です。
処理はsを1回走査するため、時間計算量はO(n)です。コストはメモリです。コピーはsと同じ長さになる可能性があり、カウンターなら不要なO(n)の追加領域を使います。
アルゴリズム
cと等しい文字をすべて取り除いたsのコピーを作ります。sの長さとコピーの長さを測ります。sの長さからコピーの長さを引いた値を返します。
def countChar(s, c):
# Every c that disappears makes the string one character shorter.
without = s.replace(c, "")
return len(s) - len(without)カウンターを使った1回のパス
考え方
コピーして数えるのはやめ、読みながら数えます。0から始まるカウンターを使って、sを左から右へたどり、現在の文字がcと等しいたびに1を加えます。一致するかどうかは単純な等価比較で判定するため、大文字が小文字に一致することはありません。
Mississippiでは、インデックス2、3、5、6でカウンターが増え、最終的に4になります。各文字は一度ずつ比較され、それ以外は何も保存されません。
これにより、時間計算量はO(n)、追加の空間計算量はO(1)です。必要なのはカウンターと対象の文字だけです。これより時間計算量を改善することはできません。読み飛ばした文字が、もう1つのcかもしれないからです。
アルゴリズム
cから対象の文字を読み取り、count = 0に設定します。sを1文字ずつ走査します。- その文字が対象の文字と等しければ、
countに1を加えます。 countを返します。
def countChar(s, c):
count = 0
for ch in s:
if ch == c:
count += 1
return count
落とし穴と境界ケース
ループは短く、バグは2つの値の比較方法に潜んでいます。
- 大文字と小文字を無視する。両方を小文字にすると、
Bananaとbの比較で1が返りますが、課題で求められているのは完全一致なので、答えは0です。 - 文字と文字列を比較する。Java、C、C++、C#、Goでは、
cは文字列として渡される一方、s.charAt(i)やs[i]は1文字です。ループの前に一度だけc[0]（またはc.charAt(0)）を取り出します。 - Javaで文字列を
==で比較する。String.valueOf(s.charAt(i)) == cはオブジェクトの同一性を比較するため、ほとんどの場合 false になります。charの値を比較するか、equalsを使います。 - Cでループ条件に
strlen(s)を呼び出す。毎回文字列全体を走査するため、5 × 10^4文字では約2.5 × 10^9回の処理が必要になります。代わりに'\0'の終端文字で停止します。
よくある質問4
文字列内にある文字の出現回数を数えるにはどうすればよいですか？
カウンターを0で初期化し、文字列を1回走査します。現在の文字が探している文字と一致するたびに、1を加えます。ループが終了すると、カウンターが答えになります。この処理の実行時間はO(n)で、追加のメモリ使用量はO(1)です。
文字を数える際、大文字と小文字は区別されますか？
この問題では、そうです。Bとbは異なる文字なので、Bananaにはbは含まれていません。大文字と小文字を区別せずに数える必要がある場合は、比較する前に文字列と文字を両方とも小文字に変換してください。
面接で組み込みの count 関数を使ってもよいですか？
通常はそうです。コストを説明できる限りは問題ありません。Python の str.countや同様の関数は文字列全体を読み取るため、O(n)です。その後、面接官からループを自分で書くよう求められることも多いので、実際に書けるように準備しておきましょう。
すべての文字を一度に数えるにはどうすればよいでしょうか？
文字列を一度走査し、ハッシュマップまたは英字52文字分のカウンターを持つ配列で、各文字の出現回数を記録します。一度走査すれば、任意の文字の出現回数を1回の検索で取得できます。同じ文字列について複数の文字を尋ねられる場合は、この方法がより適しています。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def countChar(s, c):
# ここにコードを書いてくださいケース1
ケース2
入力
s = "Mississippi" c = "s"
期待値
4