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 ثلاث مرات. يظهر كلٌّ من y (الفهرس 4) وe (الفهرس 8) مرة واحدة، وبما أن y يأتي أولًا، فالإجابة هي 4.

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

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

سؤال إضافي

تصل الأحرف واحدًا تلو الآخر من تدفّق. كيف ستُبلغ عن أول حرف فريد حتى الآن بعد وصول كل حرف؟

تلميحات

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

فُتح 0 من 3

الحل

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

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

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

الفكرة

لكل موضع بدءًا من اليسار، افحص السلسلة كاملةً بحثًا عن موضع آخر يحمل الحرف نفسه. افحص الجانبين: فالنسخة السابقة تجعل الحرف غير مؤهل بقدر ما تجعله النسخة اللاحقة غير مؤهل. أول موضع لا توجد فيه نسخة أخرى هو الإجابة. في coddycode، يجد كل موضع من 0 إلى 3 نسخةً أخرى، بينما لا يجد الحرف y عند الفهرس 4 أي نسخة.

لا يفيد التوقف عند أول نسخة عندما يظهر كل حرف في سلسلة طويلة واحدة، مثل 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 خانة عدّ لتخزين جميع التكرارات، ويُحدَّد موضع كل خانة بطرح رمز a من رمز الحرف.

تملأ الجولة الأولى خانات العدّ؛ وفي coddycode، ينتهي عدّ y وe فقط عند 1. تمرّ الجولة الثانية على السلسلة من اليسار وتتوقف عند أول حرف يكون عدّه 1، وهو y عند الفهرس 4. تمنح جولتان من n خطوة زمنًا قدره 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.
استخدام رمز الحرف الخام فهرسًا للعدّادات. قيمة a هي 97، وهي أبعد بكثير من نهاية 26 عدّادًا.
إرجاع الحرف بدلًا من فهرسه، أو إرجاع فهرس يبدأ من 1 في Lua أو R.

أسئلة شائعة3

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

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

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

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

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

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

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

اختبار #1

اختبار #2

اختبار #3

وسيط

s = "coddycode"

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