First Unique Character in a String

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

عدّ الأحرف ثم فحص السلسلة يتطلبان مرورين، يستغرق كل منهما n خطوة، لذا فالزمن هو O(n) . تشغل العدّادات الـ26 المساحة نفسها مهما كان الطول، لذا تكون المساحة الإضافية O(1) .

سهلالتجزئة

+10

لديك سلسلة نصية s تتكون من أحرف إنجليزية صغيرة. اعثر على أول حرف يظهر مرة واحدة بالضبط في السلسلة كلها، وأعِد فهرسه بدءًا من 0. إذا ظهر كل حرف أكثر من مرة، فأعِد -1.

الدالة

firstUniqChar(s: string) → integer

sstring: السلسلة المراد البحث عنها، أحرف صغيرة فقط
تُرجعinteger: فهرس أول حرف يظهر مرة واحدة بالضبط، أو ‎-1‎ إذا لم يوجد

القيود

1 ≤ s.length ≤ 5 × 10⁴
s يحتوي على أحرف إنجليزية صغيرة فقط (a إلى z).

أمثلة

المدخلات: s = "coddycode"
المخرجات: 4
الشرح: في coddycode يظهر الحرفان c وo مرتين، ويظهر d ثلاث مرات وe مرة واحدة، عند الفهرس 8. لكن y يظهر أيضًا مرة واحدة، عند الفهرس 4، ويأتي أولًا، لذا فالإجابة هي 4.

المدخلات: s = "swiss"
المخرجات: 1
الشرح: في swiss يظهر الحرف s ثلاث مرات. يظهر الحرف w عند الفهرس 1 مرة واحدة، وكذلك i عند الفهرس 2؛ يفوز الأول منهما، لذا تكون الإجابة 1.

المدخلات: s = "aabbcc"
المخرجات: -1
الشرح: يظهر كل حرف في aabbcc مرتين، لذا لا يوجد أي محرف فريد، والإجابة هي -1.

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

سؤال إضافي

تصل الأحرف واحدًا تلو الآخر من تدفّق، وبعد كل حرف عليك الإبلاغ عن أول حرف فريد حتى الآن. كيف ستحافظ على تحديث الإجابة؟

تلميحات

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

فُتح 0 من 3

الحل

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

ابحث عن نسخة ثانية من كل حرف

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

مرّ على المواضع من اليسار. عند الموضع i، افحص السلسلة كاملة بحثًا عن موضع آخر j يحمل الحرف نفسه. إذا لم تجد موضعًا كهذا، فإن s[i] فريد، وبما أنك تمر من اليسار، فهو أول حرف فريد: أَعِد i. في coddycode، يعثر كل موضع من 0 إلى 3 على نسخة أخرى، أما الموضع 4، الذي يحتوي على y، فلا يعثر على أي نسخة.

يجب أن يشمل الفحص السلسلة كاملة، قبل i وبعده. فالنسخة التي تسبق الحرف في السلسلة تستبعده بقدر ما تستبعده نسخة تأتي بعده.

يساعد التوقف عند أول نسخة في معظم السلاسل، لكن ليس كلها. عندما يتكرر كل حرف في مجموعة متصلة طويلة، مثل 2000 حرف a، ثم 2000 حرف b، وهكذا، يمرّ الفحص لكل حرف على جميع المجموعات السابقة قبل أن يعثر على نسخة منه. عندما تكون n = 5 × 10^4، يتجاوز عدد المقارنات مليارًا، وهذا بطيء جدًا للاختبارات الأكبر.

الخوارزمية

لكل فهرس i من اليسار إلى اليمين:
افحص كل فهرس j غير i، وتوقّف عند أول فهرس تكون فيه s[j] مساوية لـ s[i].
إذا لم يوجد j كهذا، فأعِد i.
إذا عُثر على نسخة لكل فهرس، فأعِد -1.

def firstUniqChar(s):
    n = len(s)
    for i in range(n):
        repeated = False
        for j in range(n):  # look for another copy of s[i]
            if j != i and s[j] == s[i]:
                repeated = True
                break
        if not repeated:
            return i
    return -1

أحصِ الحروف، ثم افحص

الفكرة

تسأل طريقة القوة الغاشمة «هل يظهر هذا الحرف في أي موضع آخر؟» من جديد عند كل موضع. احسب عدد مرات الظهور مرة واحدة بدلًا من ذلك. لا يوجد سوى 26 حرفًا، لذا تكفي مصفوفة من 26 عدّادًا لتخزين جميع الأعداد، بحيث يكون الفهرس 0 للحرف a والفهرس 25 للحرف z. فهرس الحرف هو رمز الحرف مطروحًا منه رمز a.

تمرّ المرور الأول لملء العدّادات. بالنسبة إلى coddycode، تكون القيم: c: 2 وo: 2 وd: 3 وy: 1 وe: 1. يمرّ المرور الثاني على السلسلة من اليسار ويتوقف عند أول موضع يكون فيه عدد مرات ظهور الحرف 1. هذا هو الحرف y عند الفهرس 4. يجب أن يمرّ المرور الثاني على السلسلة، لا على العدّادات الـ26، لأن السؤال يتعلق بأول موضع، لا بأول حرف في الأبجدية.

يقرأ كلا المرورين السلسلة مرة واحدة، لذا فالزمن هو O(n). يظل عدد العدّادات 26 مهما بلغ طول السلسلة، لذا فالمساحة الإضافية هي O(1).

الخوارزمية

أنشئ مصفوفة من 26 صفرًا.
لكل حرف في s، أضف 1 إلى عدّاده.
مرّ على s مرة أخرى بدءًا من الفهرس 0. أعد أول فهرس يكون عدد مرات ظهور حرفه 1.
إذا انتهى المرور، فأعد -1.

def firstUniqChar(s):
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for i, ch in enumerate(s):
        if counts[ord(ch) - ord("a")] == 1:
            return i
    return -1

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

تنشأ معظم الأخطاء من اتخاذ القرار مبكرًا جدًا أو من المرور على العنصر الخطأ في المرور الثاني.

فحص الأحرف التي تسبق الموضع i فقط. في abca، لا يوجد تكرار للحرف a الأول قبله، ومع ذلك فهو ليس فريدًا.
المرور على مصفوفة العدادات بدلًا من السلسلة النصية في المرور الثاني. في ba، ينتمي أول عداد يساوي 1 إلى a، لكن الإجابة هي الفهرس 0، أي b.
إرجاع الحرف بدلًا من فهرسه، أو إرجاع الفهرس بصيغة تبدأ من 1. يبدأ العد في Lua وR من 1، لذا اطرح 1 قبل الإرجاع.
نسيان حالة -1. سلسلة مثل aabbcc لا تحتوي على حرف فريد، ومع ذلك يجب أن تُرجع الدالة قيمة بعد انتهاء الحلقة.
فهرسة العدادات باستخدام رمز الحرف مباشرةً. قيمة a هي 97، وهي تتجاوز بكثير نهاية مصفوفة طولها 26؛ لذا اطرح رمز a أولًا.

أسئلة شائعة4

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

عدّ الأحرف ثم فحص السلسلة يتطلبان مرورين، يستغرق كل منهما n خطوة، لذا فالزمن هو O(n). تشغل العدّادات الـ26 المساحة نفسها مهما كان الطول، لذا تكون المساحة الإضافية O(1).

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

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

هل ينبغي أن تستخدم خريطة تجزئة أم مصفوفة لعدّ الحروف؟

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

لماذا تمرّ الدورة الثانية على السلسلة النصية لا على التكرارات؟

تُبيّن التكرارات الحروف الفريدة فحسب، لا مواضعها. الإجابة هي الحرف الفريد الذي يأتي أولًا في السلسلة، لذا عليك المرور على السلسلة بالترتيب والتوقف عند أول موضع يكون فيه تكرار الحرف 1.

Python

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

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

الحالة 1

الحالة 2

الحالة 3

المدخلات

s = "coddycode"

المتوقع