Count Vowels
英字で構成された文字列 s が与えられます。その文字列に含まれる母音の数を数えて、その数を返してください。母音は小文字または大文字の a、e、i、o、u です。文字 y は数えません。
関数
- sstring
- スキャンする英字の文字列
- 戻り値integer
- s に含まれる大文字と小文字を合わせた母音の数
制約
1 ≤ s.length ≤ 5 × 104sに含まれるのは英字のみです（aからz、AからZ）。
例
- 入力
- s = "Interview"
- 出力
- 4
- 説明
- 母音は
I、e、i、eです。大文字のIも小文字と同じように数えるので、答えは4です。
- 入力
- s = "rhythm"
- 出力
- 0
- 説明
rhythmにはa、e、i、o、uがありません。yは母音のように聞こえますが、リストには含まれていないため、答えは0です。
提出時に隠しテスト+18件
発展問題
文字列を一度だけ読み取りながら、5つの母音がそれぞれ何回出現するかを返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
文字を一つずつ見てください。文字が母音かどうかは何で決まり、大文字にすると答えは変わりますか？
各文字をテストする前に小文字に変換します。そうすれば、10文字ではなく5文字と比較できます。
0から始まるカウンターを保持します。各文字について、小文字に変換し、
a、e、i、o、またはuの場合はカウンターに1を加えます。
解説
カウント処理では、カウンターを使って文字列を1回走査します。判断するのは、文字が母音かどうかをどう判定するか、大文字をどう扱うかだけです。各文字を小文字に変換して5つの母音と比較すれば、各文字の処理にかかる作業量は一定です。
各母音をそれぞれ別々に数える
考え方
問題を10個の小さな問題に分けます。aはいくつあるか、eはいくつあるか、そしてUまで同様に数えます。それぞれは単純な個数です。文字列を順に調べ、探している文字と一致するたびに1を加え、最後に10個の個数を合計します。
sに含まれる母音はどれも、aeiouAEIOUの10個の文字のうちちょうど1つに一致するため、ちょうど1回だけ数えられ、子音はどれもそれらに一致しません。Interviewの場合、eの走査では2個、iの走査では1個、Iの走査では1個が見つかり、残り7回の走査では何も見つかりません。合計は4個です。
文字列を10回読み取るため、比較回数はおよそ10nです。10は定数なので、これも依然としてO(n)ですが、5 × 10^4文字の場合、1回の走査で各文字を1度ずつ読み取るのに対して、比較回数は5 × 10^5になります。
アルゴリズム
total = 0を設定します。- 10個の文字
aeiouAEIOUを1つずつ取り出します。 - それぞれの文字について、文字列全体を調べ、文字がその文字と一致するたびに
totalに1を加えます。 - 10回の処理が終わったら、
totalを返します。
def countVowels(s):
total = 0
for vowel in "aeiouAEIOU":
total += s.count(vowel) # one pass over s for this letter
return total小文字チェックを使った1回のパス
考え方
ループを逆にします。文字列を一度読み込み、各文字について1つだけ確認します。母音でしょうか？1回のチェックで大文字と小文字の両方に対応するため、まず文字を小文字に変換します。Iはiになり、Eはeになります。一方、子音は子音のままなので、5つの文字a、e、i、o、uとだけ比較すれば十分です。
チェックにかかる時間は一定です。5つの文字に対するswitch、集合での検索、または5文字の文字列aeiou内での検索を使えます。Interviewを順に見ていくと、I、e、i、eでカウンターが増え、最終的に4になります。
各文字は一度だけ読み込まれるため、時間計算量はO(n)です。メモリとして使うのはカウンターと5つの母音なので、空間計算量はO(1)です。
アルゴリズム
count = 0を設定します。- 文字列を1文字ずつ調べます。
- 文字を小文字に変換します。
a、e、i、o、またはuの場合は、countに1を加えます。countを返します。
def countVowels(s):
vowels = set("aeiou")
count = 0
for ch in s:
if ch.lower() in vowels:
count += 1
return count
落とし穴と境界ケース
このタスクは数行で解けます。見落としが起きるのは、最初のチェックで考慮されていないケースです。
- 小文字だけをチェックする。
aeiouだけと比較すると、Interviewの大文字のIを見落とし、3 を返します。文字を小文字に変換するか、10 個すべての文字を列挙してください。 yを数える。この問題ではyは決して母音ではないため、rhythmの結果は 0 です。- インデックス 0 を不一致として扱う。
"aeiou".indexOf('a')は 0 で、一致を示します。-1かどうかを判定するか、PHP では0 == falseとなるため、strposをfalseと!==で比較してください。 - C でループ条件に
strlen(s)を呼び出す。反復ごとに文字列全体を走査するため、5 × 10^4文字では約2.5 × 10^9ステップかかります。'\0'終端文字で停止するか、ループの前に一度だけ長さを計算してください。
よくある質問4
文字列内の母音を数えるにはどうすればよいですか？
カウンターを使って、文字列を一度走査します。各文字を小文字に変換し、それが a、e、i、o、または u かどうかを確認します。そうであれば、1を加算します。ループが終了すると、カウンターに答えが入っています。
母音を数える時間計算量はどれくらいですか？
これはO(n)です。ここでnは文字列の長さです。各文字を1回ずつ確認し、各確認では最大5つの文字と比較するためです。追加の空間計算量はO(1)です。カウンター1つと、固定された母音の集合を使用します。
この問題では、y は母音ですか？
いいえ。英語の綴りでは、rhythmのようにyが母音として使われることがありますが、プログラミングの問題ではほとんどの場合、母音はa、e、i、o、uと定義されており、この問題もそうです。問題にyが含まれている場合は、確認する文字に追加してください。
母音のチェックには、セット、switch、文字列検索のどれを使うべきでしょうか？
5文字の場合、3つすべてが1文字あたり一定時間で処理され、それらの速度差は気にするほどではありません。自分の言語で最も読みやすいものを選びましょう。C、C++、Goではswitch、Python、JavaScript、Rubyではセットまたは文字列検索が適しています。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def countVowels(s):
# ここにコードを書いてくださいケース1
ケース2
入力
s = "Interview"
期待値
4