Count a Character

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

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

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

+10

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

الدالة

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، لذا فالإجابة هي 4.

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

سؤال إضافي

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

تلميحات

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

فُتح 0 من 3

الحل

يمكن أن يكون أي حرف في s هو c، لذا تفحص كل حرف مرة واحدة وتعدّ الأحرف المطابقة. انتبه لحالة الأحرف: فالحرف الكبير يختلف عن الحرف الصغير.

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

الفكرة

أنشئ نسخة من s مع إزالة كل c. كل إزالة تجعل النسخة أقصر بحرف واحد، لذا فإن الفرق في الطول هو العدد. بالنسبة إلى Mississippi، تكون النسخة Miiippi: 11 ناقص 7 يساوي 4.

التعقيد الزمني هو O(n)، لكن النسخة تستهلك ذاكرة إضافية مقدارها 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)

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

الفكرة

أحصِ أثناء القراءة بدلًا من إنشاء نسخة. يبدأ العداد من 0 ويزداد بمقدار 1 لكل حرف يساوي c. تضمن المساواة العادية ألا يطابق الحرف الكبير حرفًا صغيرًا.

تتم مقارنة كل حرف مرة واحدة، ولا يُخزَّن سوى العداد: زمن O(n)، ومساحة O(1). لا يوجد حل يتفوق على زمن O(n)، لأن الحرف الذي تتجاوزه قد يكون حرف 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[i] أو s.charAt(i) هو حرف واحد. خذ c[0] (أو c.charAt(0)) مرة واحدة قبل الحلقة.
مقارنة السلاسل النصية باستخدام == في Java. تقارن String.valueOf(s.charAt(i)) == c هوية الكائن، وتكون النتيجة خاطئة في جميع الحالات تقريبًا. قارن قيم char.
استدعاء strlen(s) في شرط الحلقة في C. يعيد فحص السلسلة النصية في كل خطوة، لذا فإن 5 × 10^4 حرف تكلّف نحو 2.5 × 10^9 خطوة.

أسئلة شائعة3

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

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

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

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

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

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

def countChar(s, c):
    # اكتب الشيفرة هنا

اختبار #1

اختبار #2

الوسائط

s = "Mississippi"
c = "s"

الإخراج المتوقع