Count a Character
文字列 s と1つの文字 c が与えられます。c が s に何回出現するかを返してください。一致判定では大文字と小文字を区別します。B と b は異なる文字です。
関数
- sstring
- 検索する英字の文字列
- cstring
- 数える対象の1文字
- 戻り値integer
- s のうち c と等しい文字の数
制約
1 ≤ s.length ≤ 5 × 104sには英字（aからz、AからZ）のみが含まれます。cは英字1文字です。
例
- 入力
- s = "Mississippi"c = "s"
- 出力
- 4
- 説明
Mississippiにはインデックス2、3、5、6にsがあるので、答えは4です。
- 入力
- s = "Banana"c = "b"
- 出力
- 0
- 説明
Bananaは大文字のBで始まり、小文字のbを探しています。一致するものはないので、答えは0です。
発展問題
もしcがssのような複数の文字からなる単語だったらどうでしょうか？重なり合う一致も数えますか？また、ループはどのように変わりますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
cが何回出現するかを知るには、sのどの文字を調べる必要がありますか？sの各文字を、cとそのまま比較します。ここでは、大文字と小文字は異なる文字として扱われます。0から始まるカウンターを保持します。文字列を一度走査し、現在の文字が
cと等しい場合は1を加算します。
解説
sのどの文字もcである可能性があるので、それぞれを一度ずつ確認して、一致するものを数えます。大文字と小文字に注意してください。大文字は別の文字です。
すべての c を削除して、長さを比較します
考え方
cをすべて取り除いたsのコピーを作ります。取り除くたびにコピーは1文字短くなるので、長さの差が個数です。Mississippiの場合、コピーはMiiippiです。11から7を引くと4です。
時間計算量はO(n)ですが、コピーには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 から始まり、c と等しい各文字について 1 ずつ増えます。単純な等価比較を使うことで、大文字が小文字と一致しないようにします。
各文字は 1 回だけ比較され、保存するのはカウンターだけです。時間計算量は O(n)、空間計算量は O(1) です。O(n) より速い解法はありません。読み飛ばした文字が、もう 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
落とし穴と境界ケース
- 大文字と小文字を区別しないこと。両方を小文字にすると、
Bananaとbの比較結果は1になりますが、正解は0です。 - 文字と文字列を比較すること。Java、C、C++、C#、Goでは、
cは文字列として渡される一方、s[i]またはs.charAt(i)は1文字です。ループの前に一度だけc[0]（またはc.charAt(0)）を取り出してください。 - Javaで文字列を
==で比較すること。String.valueOf(s.charAt(i)) == cはオブジェクトの同一性を比較するため、ほとんどの場合 false になります。charの値を比較してください。 - Cでループ条件に
strlen(s)を呼び出すこと。各ステップで文字列を再走査するため、5 × 10^4文字では約2.5 × 10^9ステップかかります。
よくある質問3
文字列内の文字の出現回数を数えるにはどうすればよいですか？
0から始まるカウンターを使って文字列を1回走査し、現在の文字が数えたい文字と等しいたびに1を加えます。これにはO(n)の時間とO(1)の追加メモリが必要です。大文字と小文字を区別せずに数えるには、まず文字列と文字の両方を小文字にします。
面接で組み込みのカウント関数を使ってもよいですか？
通常はそうです。コストを説明できる限りは問題ありません。Python の str.countや同様の関数は文字列全体を読み取るため、O(n)です。面接官に尋ねられたら、ループを書けるようにしておきましょう。
すべての文字を一度に数えるにはどうすればよいでしょうか？
1回走査し、ハッシュマップまたは英字用の52個のカウンターを持つ配列で、文字ごとの個数を記録します。その走査の後は、任意の文字の個数を1回の検索で取得できます。同じ文字列内の多くの文字について尋ねられる場合に、この方法を使います。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def countChar(s, c):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
s = "Mississippi" c = "s"
期待される出力
4