Remove Vowels

Q: كيف تزيل حروف العلة من سلسلة نصية؟

مرّ على السلسلة مرة واحدة وانسخ كل حرف ليس a أو e أو i أو o أو u (بأي من الحالتين) إلى أداة إنشاء أو قائمة. ادمجها في سلسلة في النهاية. يظل ترتيب الأحرف المحفوظة وحالة أحرفها كما كانا.

Q: ما هو التعقيد الزمني لإزالة حروف العلة؟

تستغرق المرورّة الواحدة زمنًا قدره O(n) ، لأن كل محرف يخضع لاختبار ثابت الزمن للتحقق مما إذا كان حرفًا علّة. يتطلب الناتج مساحة قدرها O(n) في أسوأ الحالات، عندما لا يحتوي s على أي أحرف علّة. كما أن استدعاء replace مرة واحدة لكل حرف علّة يستغرق زمنًا قدره O(n) ، لكنه يقرأ السلسلة عشر مرات.

Q: هل يمكنك إزالة حروف العلة باستخدام تعبير نمطي؟

نعم. استبدال النمط [aeiouAEIOU] بسلسلة فارغة ينجز ذلك في استدعاء واحد في معظم اللغات. يعمل بتعقيد O(n) ، مثل الحلقة، لكن المحاورين عادةً ما يطلبون منك كتابة الحلقة حتى يتمكنوا من رؤية اختبار حروف العلة وكيفية بناء النتيجة.

مبتدئالمصفوفات والسلاسل النصية

+10

لديك سلسلة نصية s مكوّنة من أحرف إنجليزية. أعد السلسلة النصية الناتجة عن حذف كل حرف علة منها. أحرف العلة هي a وe وi وo وu، سواء كانت أحرفًا صغيرة أم كبيرة؛ ولا يُعدّ y حرف علة هنا. تحتفظ الأحرف المتبقية بترتيبها وحالة أحرفها.

الدالة

removeVowels(s: string) → string

sstring: سلسلة الأحرف الإنجليزية المطلوب تنظيفها
تُرجعstring: s بعد إزالة كل حرف علة منه، مع إبقاء الحروف الأخرى بترتيبها الأصلي

القيود

1 ≤ s.length ≤ 3 × 10⁴
s يحتوي فقط على أحرف إنجليزية (a إلى z، A إلى Z).
s يحتوي على حرف واحد على الأقل ليس من حروف العلة، لذا لا تكون الإجابة فارغة أبدًا.

أمثلة

المدخلات: s = "Interview"
المخرجات: "ntrvw"
الشرح: يؤدي حذف I وe وi وe من Interview إلى ترك n وt وr وv وw بهذا الترتيب. الحرف الكبير I حرف علة أيضًا، لذا يُحذف.

المدخلات: s = "rhythm"
المخرجات: "rhythm"
الشرح: لا تحتوي rhythm على أيٍّ من a أو e أو i أو o أو u، لذا لا يُحذف أي شيء. وحرف y فيها ليس ضمن قائمة حروف العلة، ولذلك يبقى.

المدخلات: s = "EuropeanUnion"
المخرجات: "rpnnn"
الشرح: ثمانية من الأحرف الثلاثة عشر في EuropeanUnion هي أحرف علة، بما فيها الحرفان الكبيران E وU. أما الأحرف الساكنة الخمسة المتبقية، r وp وn وn وn، فتحافظ على ترتيبها وتُقرأ rpnnn.

+17 اختبارات مخفية عند الإرسال

سؤال إضافي

ماذا لو كان النص يمكن أن يحتوي على أي حرف من أحرف Unicode، مثل É أو ö؟ أيٌّ منها حروف علة، وكيف يتغير اختبارك؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

تكون إزالة الأحرف من وسط سلسلة نصية مكلفة إذا أجريتَ عملية حذف واحدة في كل مرة، لأن كل ما يأتي بعد الفجوة ينتقل إلى مكانه. والخطة الأفضل هي إنشاء الإجابة بدلًا من ذلك: مرّ على السلسلة مرة واحدة وانسخ كل حرف ليس حرفًا متحركًا. والنقطتان اللتان يجب الانتباه إليهما هما الأحرف المتحركة الكبيرة وكيفية تجميع النتيجة.

احذف كل حرف علّة في تمريرة مستقلة

الفكرة

يمكن لمعظم اللغات حذف كل نسخة من حرف واحد من سلسلة نصية باستدعاء واحد: استبداله بلا شيء. افعل ذلك عشر مرات، مرة لكل حرف من a e i o u A E I O U، ولن يبقى أي حرف علّة. لا تُمسّ الحروف الساكنة مطلقًا، لذا تحافظ على ترتيبها وحالة أحرفها.

بالنسبة إلى Interview، تعطي العملية على e الناتج Intrviw، وتعطي العملية على i الناتج Intrvw، وتعطي العملية على I الناتج ntrvw. أما العمليات السبع الأخرى فلا تجد شيئًا تحذفه.

تقرأ كل عملية السلسلة الحالية بأكملها، لذا يبلغ العمل نحو 10n خطوةً على مستوى الأحرف. وما يزال ذلك O(n)، لأن عشرة عدد ثابت، لكن مع 3 × 10^4 حرف فهذا يعني 3 × 10^5 خطوة، بينما يحتاج المرور مرة واحدة إلى 3 × 10^4 خطوة.

الخوارزمية

تناول أحرف العلة العشرة aeiouAEIOU حرفًا واحدًا في كل مرة.
لكل حرف منها، استبدل كل نسخة منه في s بلا شيء.
بعد التمريرات العشر، أعد ما تبقى من s.

def removeVowels(s):
    for vowel in "aeiouAEIOU":
        s = s.replace(vowel, "")  # one full pass for this letter
    return s

مرور واحد يُبقي الحروف الساكنة

الفكرة

اعكس المهمة: بدلًا من حذف حروف العلة، اجمع كل ما عداها. مرّ على s مرة واحدة، واسأل عن كل حرف ما إذا كان واحدًا من حروف العلة العشرة. إذا لم يكن كذلك، فأضِفه إلى النتيجة. بما أنك تضيف الأحرف بترتيب قراءتها ولا تغيّر أي حرف، فسيكون ترتيب الحروف الساكنة وحالة أحرفها كما وردا تمامًا.

بالنسبة إلى EuropeanUnion، يتخطى المرور الأحرف E وu وo وe وa وU وi وo، ويضيف الأحرف r وp وn وn وn: فتكون النتيجة rpnnn.

تكلّف معالجة كل حرف اختبارًا واحدًا بزمن ثابت (بحثًا في مجموعة، أو switch، أو بحثًا في سلسلة من عشرة أحرف)، لذا يكون الزمن O(n). اجمع الأحرف في أداة إنشاء أو قائمة، وحوّلها إلى سلسلة مرة واحدة في النهاية؛ إذ إن تنمية سلسلة غير قابلة للتغيير باستخدام += ستؤدي إلى نسخها في كل خطوة. ويكون حجم الخرج نفسه هو مقدار المساحة O(n).

الخوارزمية

ابدأ مُنشئًا فارغًا للنتيجة.
مرّ على s حرفًا واحدًا في كل مرة.
إذا لم يكن الحرف أحد aeiouAEIOU، فأضِفه إلى المُنشئ.
أعِد المُنشئ كسلسلة نصية.

def removeVowels(s):
    vowels = set("aeiouAEIOU")
    kept = []
    for ch in s:
        if ch not in vowels:
            kept.append(ch)
    # Joining a list once avoids rebuilding the string on every character.
    return "".join(kept)

أخطاء شائعة وحالات حدّية

تأتي معظم الإجابات الخاطئة من اختبار حروف العلة أو من طريقة نمو سلسلة النتيجة.

نسيان حروف العلة الكبيرة. اختبار aeiou فقط يحوّل Interview إلى Intrvw بدلًا من ntrvw. اختبر الأحرف العشرة كلها، أو حوّل الحرف إلى أحرف صغيرة قبل الاختبار، مع الإبقاء على الحرف الأصلي في الناتج.
تغيير حالة الأحرف التي تحتفظ بها. إذا حوّلت السلسلة كلها إلى أحرف صغيرة لتقصير الاختبار، فستصبح QUEUEING qng بدلًا من QNG. حوّل النسخة التي تختبرها فقط إلى أحرف صغيرة، وأضف الحرف الأصلي.
الحذف أثناء السير إلى الأمام حسب الفهرس. إزالة s[i] تنقل الحرف التالي إلى الموضع i، ثم تتخطاه i++، لذا تصبح aab ab. أنشئ سلسلة جديدة، أو استخدم موضعي قراءة وكتابة منفصلين.
زيادة طول سلسلة غير قابلة للتغيير باستخدام += داخل حلقة. في Java أو C# تنسخ كل خطوة السلسلة بأكملها، أي نحو 4.5 × 10^8 عملية نسخ للأحرف عند وجود 3 × 10^4 حرفًا. استخدم أداة إنشاء سلاسل أو قائمة، ثم ادمج عناصرها مرة واحدة.

أسئلة شائعة4

كيف تزيل حروف العلة من سلسلة نصية؟

مرّ على السلسلة مرة واحدة وانسخ كل حرف ليس a أو e أو i أو o أو u (بأي من الحالتين) إلى أداة إنشاء أو قائمة. ادمجها في سلسلة في النهاية. يظل ترتيب الأحرف المحفوظة وحالة أحرفها كما كانا.

ما هو التعقيد الزمني لإزالة حروف العلة؟

تستغرق المرورّة الواحدة زمنًا قدره O(n)، لأن كل محرف يخضع لاختبار ثابت الزمن للتحقق مما إذا كان حرفًا علّة. يتطلب الناتج مساحة قدرها O(n) في أسوأ الحالات، عندما لا يحتوي s على أي أحرف علّة. كما أن استدعاء replace مرة واحدة لكل حرف علّة يستغرق زمنًا قدره O(n)، لكنه يقرأ السلسلة عشر مرات.

هل يمكنك إزالة حروف العلة باستخدام تعبير نمطي؟

نعم. استبدال النمط [aeiouAEIOU] بسلسلة فارغة ينجز ذلك في استدعاء واحد في معظم اللغات. يعمل بتعقيد O(n)، مثل الحلقة، لكن المحاورين عادةً ما يطلبون منك كتابة الحلقة حتى يتمكنوا من رؤية اختبار حروف العلة وكيفية بناء النتيجة.

لماذا لا تحذف حروف العلة من السلسلة مباشرةً؟

حذف حرف واحد من الوسط يُزيح كل حرف لاحق إلى اليسار، لذلك قد تستغرق عمليات الحذف الكثيرة O(n²). يمكنك إجراء ذلك في المكان نفسه بتعقيد O(n) باستخدام فهرسين: أحدهما يقرأ كل حرف، والآخر يكتب الحرف التالي الذي سيتم الاحتفاظ به، لكن في معظم اللغات لا يمكن تغيير السلاسل النصية، لذا فإن إنشاء سلسلة نصية جديدة هو الخيار الطبيعي.

Python

def removeVowels(s):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

s = "Interview"

المتوقع

"ntrvw"