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 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك إرجاع عدد مرات ظهور كل حرف من حروف العلة الخمسة، مع الاستمرار في قراءة السلسلة مرة واحدة فقط؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
انظر إلى الأحرف واحدًا تلو الآخر. ما الذي يجعل الحرف حرفًا متحركًا، وهل يغيّر استخدام الأحرف الكبيرة الإجابة؟
حوّل كل حرف إلى أحرف صغيرة قبل اختباره. ثم قارنه بخمسة أحرف بدلًا من عشرة.
احتفِظ بعدّاد يبدأ من 0. لكل حرف، حوِّله إلى أحرف صغيرة وأضِف 1 إلى العدّاد عندما يكون
aأوeأوiأوoأوu.
الحل
يتم العدّ بتمرير واحد على السلسلة النصية مع استخدام عدّاد. والقراران الوحيدان هما كيفية اختبار ما إذا كان الحرف حرف علة، وما يجب فعله مع الأحرف الكبيرة. حوّل كل حرف إلى صيغة الأحرف الصغيرة وقارنه بأحرف العلة الخمسة، وستتطلب معالجة كل حرف مقدارًا ثابتًا من العمل.
احسب كل حرف علة في تمريرة منفصلة
الفكرة
قسّم السؤال إلى عشرة أسئلة أصغر: كم عدد أحرف a، وكم عدد أحرف e، وهكذا حتى U. كل واحد من هذه الأسئلة يتعلق بعدّ بسيط. مرّ على السلسلة وأضف 1 كلما كان الحرف يساوي الحرف الذي تبحث عنه، ثم اجمع الأعداد العشرة.
كل حرف علة في s يساوي حرفًا واحدًا بالضبط من الأحرف العشرة في aeiouAEIOU، لذا يُحصى مرة واحدة بالضبط، ولا يساوي أي حرف ساكن أيًّا منها. في Interview، يعثر المرور الخاص بـ e على 2، والمرور الخاص بـ i على 1، والمرور الخاص بـ I على 1، ولا يعثر أيٌّ من المرورّات السبعة الأخرى على شيء: المجموع 4.
تُقرأ السلسلة عشر مرات، أي نحو 10n مقارنة. يظل ذلك 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 وE إلى e، بينما تبقى الحروف الساكنة كما هي، لذا لا تحتاج إلا إلى المقارنة مع الأحرف الخمسة a وe وi وo وu.
يستغرق الفحص وقتًا ثابتًا: باستخدام switch للأحرف الخمسة، أو البحث في مجموعة، أو البحث في السلسلة ذات الأحرف الخمسة aeiou. عند المرور على Interview، يزداد العداد عند I وe وi وe، وينتهي عند 4.
يُقرأ كل حرف مرة واحدة، لذا فالزمن هو 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. في هذه المسألة، لا يُعدّ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خطوة. توقّف عند المُنهي'\0'، أو احسب الطول مرة واحدة قبل الحلقة.
أسئلة شائعة4
كيف تحسب حروف العلة في سلسلة نصية؟
مرّر على السلسلة مرة واحدة باستخدام عدّاد. حوّل كل حرف إلى الأحرف الصغيرة وتحقّق مما إذا كان a أو e أو i أو o أو u؛ وإذا كان كذلك، فأضف 1. عند انتهاء الحلقة، يحتوي العدّاد على الإجابة.
ما التعقيد الزمني لعدّ حروف العلة؟
إنه O(n)، حيث إن n هو طول السلسلة، لأن كل حرف يُفحَص مرة واحدة، وكل فحص يقارن مع خمسة أحرف كحد أقصى. المساحة الإضافية هي O(1): عدّاد واحد ومجموعة ثابتة من حروف العلة.
هل يُعدّ y حرفًا متحركًا في هذه المسألة؟
لا. في التهجئة الإنجليزية، يعمل y أحيانًا كحرف علة، كما في rhythm، لكن مسائل البرمجة غالبًا ما تعرّف حروف العلة بأنها a وe وi وo وu، وهذه المسألة تفعل ذلك. إذا تضمنت المسألة y، فأضِفه إلى الحروف التي تتحقق منها.
هل ينبغي أن يستخدم التحقق من حروف العلة مجموعةً أم جملة switch أم بحثًا في سلسلة نصية؟
تتكوّن جميعها من خمسة أحرف، وتستغرق وقتًا ثابتًا لكل حرف، والفرق في السرعة بينها صغير جدًا بحيث لا يُعتدّ به. اختر ما يبدو أوضح عند قراءته بلغتك: عبارة switch في C أو C++ أو Go، أو مجموعة أو بحثًا في سلسلة نصية في Python أو JavaScript أو Ruby.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def countVowels(s):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
s = "Interview"
المتوقع
4