Count a Character

Q: هل يُراعى اختلاف حالة الأحرف عند عدّ المحارف؟

في هذه المسألة، نعم: يُعدّ B و b حرفين مختلفين، لذا لا تحتوي Banana على b . إذا كنت بحاجة إلى عدّ غير حساس لحالة الأحرف، فحوّل السلسلة والحرف إلى أحرف صغيرة قبل المقارنة.

Q: هل يمكنني استخدام دالةّ العدّ المضمّنة في مقابلة؟

عادةً نعم، ما دمت تستطيع توضيح تكلفتها. لا تزال الدالة str.count في Python والدوال المشابهة تقرأ السلسلة كاملة، لذا يكون تعقيدها O(n) . ثم يطلب منك كثير من القائمين على المقابلات كتابة الحلقة بنفسك، لذا كن مستعدًا لعرضها.

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

+10

لديك سلسلة نصية s وحرف واحد c. أعد عدد مرات ظهور c في s. المطابقة حساسة لحالة الأحرف: B وb حرفان مختلفان، لذا تُحتسب فقط المطابقات التامة لـ c.

الدالة

countChar(s: string, c: string) → integer

sstring: سلسلة الأحرف الإنجليزية المراد البحث عنها
cstring: الحرف الواحد المراد عده
تُرجعinteger: كم عدد الأحرف في s التي تساوي c

القيود

1 ≤ s.length ≤ 5 × 10⁴
s يحتوي على أحرف إنجليزية فقط (a إلى z، وA إلى Z).
c هو حرف إنجليزي واحد بالضبط.

أمثلة

المدخلات: s = "Mississippi"c = "s"
المخرجات: 4
الشرح: تحتوي Mississippi على s في المواضع 2 و3 و5 و6، عند العد بدءًا من 0، لذا فالإجابة هي 4.

المدخلات: s = "Banana"c = "b"
المخرجات: 0
الشرح: تبدأ Banana بحرف B كبير، بينما البحث عن حرف b صغير. الحرفان مختلفان، لذا لا يتطابق أي شيء، والإجابة هي 0.

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

سؤال إضافي

ماذا لو أمكن أن تكون c كلمةً مكوّنةً من عدة أحرف، مثل ss؟ هل تُحتسب المطابقات المتداخلة، وكيف تتغير الحلقة؟

تلميحات

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

فُتح 0 من 3

الحل

يجب النظر إلى كل حرف من s مرة واحدة، لأن أيًا منها قد يكون c. تتم العملية بتمريرة واحدة مع عدّاد. والتفاصيل التي قد تربك البعض هي حالة الأحرف (فالحرف الكبير يختلف عن الحرف الصغير) وفي بعض اللغات، مقارنة حرف بسلسلة نصية مكوّنة من حرف واحد.

احذف كل c وقارن الأطوال

الفكرة

أنشئ نسخة من s مع حذف كل c. يجعل كل حرف محذوف النسخة أقصر بحرف واحد، لذا فإن الفرق بين الطولين يساوي تمامًا عدد مرات ظهور c. تحتوي معظم اللغات على دالة استبدال أو حذف تُجري الإزالة نيابةً عنك.

بالنسبة إلى Mississippi وs، تكون النسخة Miiippi. وهذا يعني 7 أحرف مقابل الأحرف الـ11 في الأصل، لذا ظهر c أربع مرات. أما مع Banana وb، فلا يُحذف شيء لأن B الكبيرة لا تطابق b، ويكون الفرق 0.

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

الخوارزمية

أنشئ نسخة من s تحذف كل محرف يساوي c.
احسب طول s وطول النسخة.
أعِد طول s ناقص طول النسخة.

def countChar(s, c):
    # Every c that disappears makes the string one character shorter.
    without = s.replace(c, "")
    return len(s) - len(without)

مرور واحد باستخدام عدّاد

الفكرة

تجاوز النسخ والعدّ أثناء القراءة. مرّ على s من اليسار إلى اليمين باستخدام عدّاد يبدأ من 0، وأضف 1 كلما كان الحرف الحالي مساويًا لـ c. تُحدَّد المطابقة بالمساواة العادية، لذا لا يتطابق الحرف الكبير أبدًا مع حرف صغير.

في Mississippi، يرتفع العدّاد عند الفهارس 2 و3 و5 و6، وينتهي عند 4. تتم مقارنة كل حرف مرة واحدة، ولا يُخزَّن أي شيء آخر.

هذا يعني زمنًا قدره O(n) ومساحة إضافية قدرها O(1): عدّادًا واحدًا والحرف المستهدف. لا يمكنك تحقيق زمن أفضل، لأن الحرف الذي تتجاوزه قد يكون حرف c إضافيًا.

الخوارزمية

اقرأ الحرف المستهدف من c واضبط count = 0.
مرّ على s حرفًا واحدًا في كل مرة.
إذا كان الحرف يساوي الحرف المستهدف، فأضف 1 إلى count.
أعِد count.

def countChar(s, c):
    count = 0
    for ch in s:
        if ch == c:
            count += 1
    return count

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

الحلقة قصيرة، وتكمن الأخطاء في طريقة مقارنة القيمتين.

تجاهل حالة الأحرف. تحويل كلا الطرفين إلى أحرف صغيرة يجعل Banana مع b يعيدان 1، لكن المطلوب هو التطابق التام، لذا تكون الإجابة 0.
مقارنة محرف بسلسلة نصية. في Java وC وC++ وC# وGo، تكون c سلسلة نصية، بينما يكون s.charAt(i) أو s[i] محرفًا واحدًا. استخدم c[0] (أو c.charAt(0)) مرة واحدة قبل الحلقة.
مقارنة السلاسل النصية باستخدام == في Java. تقارن String.valueOf(s.charAt(i)) == c هوية الكائن، وتكون النتيجة خاطئة في معظم الحالات. قارن قيم char، أو استخدم equals.
استدعاء strlen(s) في شرط الحلقة في C. إذ تمر على السلسلة النصية بأكملها في كل خطوة، لذا فإن 5 × 10^4 محرف تكلّف نحو 2.5 × 10^9 خطوة. توقّف عند المُنهي '\0' بدلًا من ذلك.

أسئلة شائعة4

كيف تحصي مرات ظهور حرف في سلسلة نصية؟

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

هل يُراعى اختلاف حالة الأحرف عند عدّ المحارف؟

في هذه المسألة، نعم: يُعدّ B وb حرفين مختلفين، لذا لا تحتوي Banana على b. إذا كنت بحاجة إلى عدّ غير حساس لحالة الأحرف، فحوّل السلسلة والحرف إلى أحرف صغيرة قبل المقارنة.

هل يمكنني استخدام دالةّ العدّ المضمّنة في مقابلة؟

عادةً نعم، ما دمت تستطيع توضيح تكلفتها. لا تزال الدالة str.count في Python والدوال المشابهة تقرأ السلسلة كاملة، لذا يكون تعقيدها O(n). ثم يطلب منك كثير من القائمين على المقابلات كتابة الحلقة بنفسك، لذا كن مستعدًا لعرضها.

كيف يمكنك عدّ كل حرف دفعةً واحدة؟

أجرِ مرورًا واحدًا واحتفظ بعدٍّ لكل حرف، في خريطة تجزئة أو في مصفوفة تضم 52 عدّادًا للأحرف الإنجليزية. بعد هذا المرور، يصبح عدد أي حرف متاحًا بعملية بحث واحدة. هذه هي الخطة الأفضل عندما يُطلب منك الاستعلام عن أحرف عديدة في السلسلة النصية نفسها.

Python

def countChar(s, c):
    # اكتب الكود هنا

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

الحالة 1

الحالة 2

المدخلات

s = "Mississippi"
c = "s"

المتوقع