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.
سؤال إضافي
هل يمكنك إرجاع عدد مرات ظهور كل واحد من أحرف العلة الخمسة، مع قراءة السلسلة مرة واحدة فقط؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
انظر إلى الأحرف واحدًا تلو الآخر. ما الذي يجعل الحرف حرفًا علّة، وهل يغيّر استخدام الأحرف الكبيرة الإجابة؟
حوّل كل حرف إلى أحرف صغيرة قبل اختباره. ثم قارنه بخمسة أحرف بدلًا من عشرة.
احتفِظ بعدّاد يبدأ من 0. لكل حرف، حوّله إلى أحرف صغيرة وأضف 1 إلى العدّاد عندما يكون
aأوeأوiأوoأوu.
الحل
اقرأ السلسلة النصية مرة واحدة باستخدام عدّاد. حوّل كل حرف إلى أحرف صغيرة، بحيث يغطي فحص واحد للحروف المتحركة الخمسة كلا الحالتين.
عُدَّ كلَّ حرفٍ علّةٍ في مرورٍ مستقل
الفكرة
عُدَّ كلًّا من الأحرف العشرة في aeiouAEIOU في مرور مستقل على السلسلة، ثم اجمع الأعداد العشرة. كل حرف علّة يطابق حرفًا واحدًا بالضبط من الأحرف العشرة، لذا يُعَدّ مرة واحدة، ولا يطابق أي حرف ساكن أيًّا منها.
تُقرأ السلسلة عشر مرات. يظل ذلك O(n)، لكن بالنسبة إلى 5 × 10^4 حرف، فهذا يعني 5 × 10^5 مقارنة، في حين يقرأ المرور الواحد كل حرف مرة واحدة.
الخوارزمية
- عيّن
total = 0. - تناول الأحرف العشرة
aeiouAEIOUواحدًا تلو الآخر. - لكل حرف، افحص السلسلة بأكملها وأضف 1 إلى
totalكلما ساوى أحد الأحرف ذلك الحرف. - بعد المرور على الأحرف العشرة، أعد
total.
def countVowels(s):
total = 0
for vowel in "aeiouAEIOU":
total += s.count(vowel) # one pass over s for this letter
return totalمرور واحد مع التحقق من الأحرف الصغيرة
الفكرة
اقرأ السلسلة مرة واحدة، واسأل عن كل حرف ما إذا كان حرف علة. تحويلها إلى أحرف صغيرة أولًا يحوّل I إلى i ويُبقي الحروف الساكنة حروفًا ساكنة، لذا تقارن بخمسة أحرف بدلًا من عشرة.
يستغرق الفحص وقتًا ثابتًا: switch أو البحث في مجموعة أو البحث في السلسلة aeiou. يُقرأ كل حرف مرة واحدة، ولا يُخزَّن سوى عدّاد: زمن O(n) ومساحة O(1).
الخوارزمية
- عيّن
count = 0. - مرّ على السلسلة حرفًا واحدًا في كل مرة.
- حوّل الحرف إلى أحرف صغيرة.
- إذا كان
aأوeأوiأوoأوu، فأضف 1 إلىcount. - أعِد
count.
def countVowels(s):
vowels = set("aeiou")
count = 0
for ch in s:
if ch.lower() in vowels:
count += 1
return count
أخطاء شائعة وحالات حدّية
- فحص الأحرف الصغيرة فقط. المقارنة مع
aeiouوحدها تفوّت الحرف الكبيرIفيInterviewوتُرجع 3. - احتساب
y. هنا لا يُعدّ حرفًا متحركًا أبدًا، لذا تُعطيrhythmالقيمة 0. - اعتبار الفهرس 0 عدمَ تطابق. تُعطي
"aeiou".indexOf('a')القيمة 0، وهذا تطابق. تحقّق من-1، أو في PHP قارِنstrposمعfalseباستخدام!==، لأن0 == falseفي PHP. - استدعاء
strlen(s)في شرط الحلقة في C. فهذا يعيد فحص السلسلة في كل خطوة، لذا فإن5 × 10^4حرف تكلّف نحو2.5 × 10^9خطوة.
أسئلة شائعة3
كيف تحسب عدد حروف العلة في سلسلة نصية؟
مرّر على السلسلة النصية مرة واحدة باستخدام عدّاد. حوّل كل حرف إلى أحرف صغيرة وأضف 1 إذا كان a أو e أو i أو o أو u. عند انتهاء الحلقة، يحتوي العدّاد على الإجابة.
ما هو التعقيد الزمني لعدّ حروف العلة؟
O(n)، حيث إن n هو طول السلسلة، لأن كل حرف يُفحَص مرة واحدة مقابل خمسة أحرف كحد أقصى. المساحة الإضافية هي O(1): عدّاد واحد ومجموعة ثابتة من حروف العلة.
هل يُعدّ الحرف y حرفًا متحركًا في هذه المسألة؟
لا. في التهجئة الإنجليزية، تؤدي y أحيانًا دور حرف علة، كما في rhythm، لكن مسائل البرمجة تعرّف أحرف العلة دائمًا تقريبًا بأنها a وe وi وo وu، وهذه المسألة تفعل ذلك. إذا تضمنت المسألة y، فأضِفها إلى الأحرف التي تتحقق منها.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def countVowels(s):
# اكتب الشيفرة هنااختبار #1
اختبار #2
وسيط
s = "Interview"
الإخراج المتوقع
4