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です。
発展問題
文字列を一度だけ読み取って、5つの母音それぞれが何回現れるかを返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
文字を1つずつ見てみましょう。文字が母音であるかどうかは何で決まり、大文字にすると答えは変わるでしょうか？
テストする前に各文字を小文字に変換します。そうすれば、10個ではなく5個の文字と比較できます。
0から始まるカウンターを保持します。各文字を小文字にし、それが
a、e、i、o、またはuの場合はカウンターに1を加えます。
解説
カウンターを使って文字列を一度読み取ります。各文字を小文字に変換すれば、5つの母音を一度確認するだけで大文字と小文字の両方を扱えます。
母音をそれぞれ別のパスで数える
考え方
aeiouAEIOUに含まれる10個の文字をそれぞれ文字列を一巡して数え、その10個の個数を合計します。各母音は10個の文字のうちちょうど1つに該当するため、1回だけ数えられ、子音はいずれにも該当しません。
文字列は10回読み取られます。それでも計算量はO(n)ですが、5 × 10^4個の文字に対しては、各パスで各文字を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回のパス
考え方
文字列を一度読み込み、各文字が母音かどうかを確認します。最初に小文字に変換すると、I は i になり、子音は子音のままなので、10文字ではなく5文字と比較すればよくなります。
確認にかかる時間は一定です。switch、集合の検索、または文字列 aeiou の検索を使います。各文字は一度だけ読み込み、保存するのはカウンターだけです。時間計算量は O(n)、空間計算量は 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を返します。 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ステップかかります。
よくある質問3
文字列内の母音の数をどうやって数えますか？
カウンターを使って文字列を1回走査します。各文字を小文字に変換し、それがa、e、i、o、またはuの場合は1を加えます。ループが終わると、カウンターに答えが格納されています。
母音を数える時間計算量はどれくらいですか？
O(n)。ここでnは文字列の長さです。各文字は最大5つの文字と1回ずつ照合されるためです。追加の領域はO(1)です。カウンター1つと、固定された母音の集合を使用します。
この問題では y は母音ですか？
いいえ。英語の綴りでは、rhythm のように y が母音として働くことがありますが、プログラミングの問題では、母音をほぼ必ず a、e、i、o、u と定義しており、この問題もそうです。問題に y が含まれている場合は、チェックする文字に追加してください。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def countVowels(s):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
s = "Interview"
期待される出力
4