Permutation in String

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

باستخدام نافذة منزلقة، يكون التعقيد O(m + n) ، حيث إن m هو طول s1 و n هو طول s2 . تحسب s1 مرة واحدة، ثم يدخل كل حرف من s2 النافذة مرة واحدة ويخرج منها مرة واحدة. أما إعادة العد من البداية لكل نافذة فتكلف O(n · m) بدلًا من ذلك.

Q: هل تعني مسألة «التبديل في سلسلة نصية» العثور على كلمة مُعاد ترتيب حروفها داخل سلسلة نصية؟

نعم. التبديل الترتيبي لـ s1 هو مقلوبٌ حرفيٌّ له، لذا فالسؤال هو ما إذا كانت هناك سلسلة فرعية من s2 بطول m تكون مقلوبًا حرفيًا لـ s1 . تقارن عملية التحقق من المقلوب الحرفي بين سلسلتين كاملتين عدد مرات ظهور الأحرف مرة واحدة؛ أما هنا، فتُجرى المقارنة نفسها على نافذة تنزلق على طول s2 .

Q: لماذا تكون النافذة المنزلقة ذات حجم ثابت هنا؟

يحتوي كل تبديل لـ s1 على m أحرف بالضبط، لذا لا يمكن أن تتطابق إلا النوافذ ذات الطول m . مسائل مثل أطول سلسلة فرعية بلا أحرف مكررة تكبّر النافذة وتصغّرها؛ أما هنا فيتحرك الطرفان معًا، خطوةً واحدةً في كل مرة.

متوسطالنافذة المنزلقة التجزئة

+10

تستخدم تبديلة السلسلة الحروف نفسها بأي ترتيب، ويظهر كل حرف فيها بعدد مرات ظهوره في السلسلة الأصلية: tar وrat وart تبديلات بعضها لبعض. لديك سلسلتان s1 وs2 مكوّنتان من أحرف إنجليزية صغيرة. أعد true إذا ظهرت أي تبديلة من s1 في s2 كسلسلة فرعية (تتابع من الأحرف المتجاورة)، وأعد false خلاف ذلك.

الدالة

checkInclusion(s1: string, s2: string) → boolean

s1string: الحروف المطلوب إعادة ترتيبها
s2string: السلسلة النصية التي سيتم البحث فيها
تُرجعboolean: صحيح إذا كانت سلسلة فرعية من s2 إعادة ترتيب لـ s1

القيود

1 ≤ s1.length ≤ 2 × 10⁴
1 ≤ s2.length ≤ 5 × 10⁴
s1 وs2 يحتويان على أحرف إنجليزية صغيرة فقط (a إلى z).
s1 قد تكون أطول من s2.

أمثلة

المدخلات: s1 = "tar"s2 = "smartphone"
المخرجات: true
الشرح: السلسلة الفرعية art عند الفهارس من 2 إلى 4 في smartphone تحتوي على حرف a واحد، وحرف r واحد، وحرف t واحد، وهي الأحرف نفسها الموجودة في tar.

المدخلات: s1 = "noon"s2 = "onion"
المخرجات: false
الشرح: المقاطع الفرعية ذات الطول 4 هي onio وnion. تتطلب noon حرفَي n وحرفَي o، وتحتوي كل نافذة على i بدلًا من أحدهما. تظهر جميع أحرف noon في onion، لكن لا تحتوي أي نافذة على الأعداد الصحيحة من الأحرف.

المدخلات: s1 = "abcd"s2 = "dcb"
المخرجات: false
الشرح: أي ترتيب مختلف للأحرف abcd يتكوّن من 4 أحرف، بينما يتكوّن dcb من 3 أحرف فقط، لذا لا يمكن أن يحتوي على ترتيبٍ منها.

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

سؤال إضافي

هل يمكنك إرجاع جميع الفهارس في s2 التي يبدأ عندها تبديل لـ s1، مع الحفاظ على زمن O(m + n)؟

تلميحات

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

فُتح 0 من 3

الحل

إن سرد جميع تبديلات s1 أمر ميؤوس منه: فحتى 10 أحرف لها 3,628,800 ترتيبًا. والحل هو التوقف عن الاهتمام بالترتيب. تكون سلسلة فرعية من s2 تبديلًا لـ s1 بالضبط عندما يكون لها الطول نفسه m والعدد نفسه من كل حرف. لذلك، كل احتمال هو نافذة بطول ثابت واحد، ويمكنك تحريك نافذة واحدة عبر s2، مع تحديث أعداد أحرفها بإدخال حرف وإخراج حرف في كل خطوة.

عُدَّ كل نافذة من البداية

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

الفكرة

إن القراءة الحرفية، أي بناء كل تبديل ممكن لـ s1 والبحث عنه، تفشل فورًا: فترتيب 20 حرفًا له أكثر من 2 × 10^18 احتمالًا. بدلًا من ذلك، أعد صياغة السؤال. تكون سلسلة فرعية من s2 تبديلًا لـ s1 عندما تحتوي على m حرفًا بالضبط، وتستخدم كل حرف بعدد مرات ظهوره نفسه في s1. أما ترتيب الأحرف فيها فلا يهم إطلاقًا.

لذا، احسب أحرف s1 مرة واحدة في جدول من 26 عددًا، يكون فيه الفهرس 0 للحرف a و25 للحرف z. ثم خذ كل سلسلة فرعية من s2 طولها m، واحسب أحرفها في جدول جديد، وقارن الجدولين. بالنسبة إلى tar في smartphone، تكون النوافذ sma وmar وart وما إلى ذلك، وتطابق art: حرف a واحد، وحرف r واحد، وحرف t واحد.

هذه الطريقة صحيحة لأنها تفحص كل احتمال. لكنها بطيئة لأن النوافذ المتجاورة تشترك في m-1 حرفًا، وأنت تعيد عدّها كلها. عندما تكون m = 15,000 وn = 50,000، يوجد 35,001 نافذة، طول كل منها 15,000 حرف، أي نحو 5 × 10^8 خطوة.

الخوارزمية

إذا كان s1 أطول من s2، فأرجِع false.
احسب حروف s1 في جدول need مكوّن من 26 صفرًا.
لكل فهرس بداية من 0 إلى n-m، احسب حروف الأحرف الـm بدءًا من ذلك الفهرس في جدول جديد.
إذا كان هذا الجدول مساويًا لـneed، فأرجِع true.
بعد النافذة الأخيرة، أرجِع false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26  # need[0] is 'a', need[25] is 'z'
    for ch in s1:
        need[ord(ch) - 97] += 1
    for start in range(n - m + 1):
        # Count the letters of s2[start : start + m] from scratch
        window = [0] * 26
        for i in range(start, start + m):
            window[ord(s2[i]) - 97] += 1
        if window == need:
            return True
    return False

حرّك النافذة وقارن بين 26 عددًا

الفكرة

تختلف نافذتان متجاورتان في حرفين فقط. فالانتقال من mar إلى art يزيل m من اليسار ويضيف t من اليمين. لذا احتفظ بجدول واحد للنافذة الحالية وغيّره بإضافة واحدة (+1) وحذف واحدة (-1) في كل خطوة، بدلًا من إعادة عدّ الأحرف m.

املأ need من s1 وwindow من الأحرف m الأولى في s2، ثم قارنهما. بعد ذلك، لكل i من m إلى n-1، أضف s2[i]، وأزل s2[i-m]، ثم قارن مرة أخرى. تصبح النافذة الآن s2[i-m+1..i]، ويظل طولها m حرفًا.

تتطلب كل خطوة تحديثين ومقارنة 26 رقمًا، أيًا كانت قيمة m. في أكبر مُدخل، يعادل ذلك نحو 26 × 50,000 = 1.3 × 10^6 عملية، وهو خطي بالنسبة إلى طول s2. هذا هو الحل الذي يتوقعه معظم القائمين على المقابلات.

الخوارزمية

إذا كان طول s1 أكبر من طول s2، فأعِد false.
احسب أحرف s1 في need وأول m أحرف من s2 في window.
إذا كان الجدولان متساويين، فأعِد true.
لكل i من m إلى n-1: أضف 1 إلى s2[i]، واطرح 1 من s2[i-m]، وأعِد true إذا كان الجدولان متساويين.
أعِد false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26
    window = [0] * 26
    for i in range(m):
        need[ord(s1[i]) - 97] += 1
        window[ord(s2[i]) - 97] += 1  # the first window is s2[0 : m]
    if window == need:
        return True
    for i in range(m, n):
        window[ord(s2[i]) - 97] += 1      # s2[i] enters on the right
        window[ord(s2[i - m]) - 97] -= 1  # s2[i - m] leaves on the left
        if window == need:
            return True
    return False

حرّك النافذة وتتبّع الأحرف غير المتوازنة

الفكرة

إن مقارنة 26 رقمًا في كل خطوة تكرر العمل، لأن الخطوة تغيّر رقمين فقط. احتفظ بجدول واحد balance بدلًا من ذلك: يعبّر balance[c] عن عدد مرات ظهور الحرف c في s1 مطروحًا منه عدد مرات ظهوره في النافذة. تكون النافذة تبديلًا لـ s1 بالضبط عندما تكون القيم الـ26 كلها 0. وبجانب الجدول، احتفظ بـ unbalanced، وهو عدد الأحرف التي لا يساوي رصيدها 0، وأعِد true فور وصوله إلى 0.

لعملية التتبع قاعدة واحدة. قبل تغيير balance[c]، إذا كانت قيمته 0، فهذا يعني أن الحرف على وشك أن يخرج عن التوازن، لذا أضف 1 إلى unbalanced. بعد التغيير، إذا أصبحت قيمته 0، فهذا يعني أن الحرف قد عاد إلى التوازن، لذا اطرح 1. دخول حرف إلى النافذة يخفض رصيده بمقدار 1؛ وخروجه منها يرفع رصيده بمقدار 1. الانتقال بالرصيد من 2 إلى 1 لا يفعّل أيًا من الفحصين، وهذا صحيح: فالحرف كان غير متوازن وما زال كذلك.

تتبّع tar وsmartphone. تبدأ الأرصدة هكذا: a: 1، r: 1، t: 1، لذا تكون قيمة unbalanced هي 3. يدخل الحرفان s وm فترتفع إلى 5، ثم يدخل a ويصبح رصيده 0: فتنخفض إلى 4. يدخل r (3) بينما يخرج s (2). يدخل t (1) بينما يخرج m (0)، وتكون النافذة art هي الإجابة.

يمكنك اختبار unbalanced == 0 بدءًا من الحرف الأول. ما دامت النافذة تحتوي على أقل من m حرفًا، يكون مجموع الأرصدة عددًا موجبًا، لذا لا بد أن تكون قيمة رصيد واحدة على الأقل غير 0. تنفّذ كل خطوة مقدارًا ثابتًا من العمل، لذا يكون المسح كاملًا O(m + n)، ويحتوي الجدول دائمًا على 26 رقمًا، أي إن المساحة المستخدمة هي O(1).

الخوارزمية

إذا كان s1 أطول من s2، فأعِد false.
احسب أحرف s1 في balance، واجعل unbalanced عدد الأحرف التي يختلف توازنها عن 0.
لكل فهرس i في s2، اطرح 1 من توازن s2[i]، وأضف 1 إلى unbalanced إذا كان ذلك التوازن 0، واطرح 1 إذا أصبح 0.
إذا كان i ≥ m، فأضف 1 إلى توازن s2[i-m] مع إجراء الحساب نفسه.
إذا كانت قيمة unbalanced تساوي 0، فأعِد true. بعد انتهاء الحلقة، أعِد false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    # balance[c]: copies of letter c in s1 minus copies in the window
    balance = [0] * 26
    for ch in s1:
        balance[ord(ch) - 97] += 1
    unbalanced = sum(1 for b in balance if b != 0)
    for i in range(n):
        # s2[i] enters the window on the right
        c = ord(s2[i]) - 97
        if balance[c] == 0:
            unbalanced += 1
        balance[c] -= 1
        if balance[c] == 0:
            unbalanced -= 1
        # s2[i - m] leaves on the left once the window would pass m letters
        if i >= m:
            c = ord(s2[i - m]) - 97
            if balance[c] == 0:
                unbalanced += 1
            balance[c] += 1
            if balance[c] == 0:
                unbalanced -= 1
        if unbalanced == 0:
            return True
    return False

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

تأتي معظم الإجابات الخاطئة من أطراف النافذة، أو من التحقق من الحروف الموجودة بدلًا من عدد مرات ظهورها.

التحقق فقط من أن كل حرف في s1 موجود في النافذة. تحتوي onio على كل حروف noon، لكنها ليست تبديلًا لها. قارن التكرارات.
إزالة الحرف الخطأ. عندما يدخل s2[i]، يكون الحرف الذي يخرج هو s2[i-m]، لذا تصبح النافذة s2[i-m+1..i]. تؤدي إزالة s2[i-m+1] إلى ترك نافذة من m-1 حرفًا.
تخطي النافذة الأولى. إذا أجريت المقارنة بعد تحريك النافذة فقط، فلن يُعثر أبدًا على تبديل يبدأ عند الفهرس 0.
نسيان الحالة التي يكون فيها s1 أطول من s2. في Rust، يؤدي n - m على أطوال غير موقعة إلى تجاوز سفلي، وفي Swift يتسبب النطاق 0...(n - m) في حدوث خطأ. أعد false أولًا.
مقارنة المصفوفات باستخدام == في لغة تقارن فيها هذه العملية المراجع. في JavaScript وDart، لا تتساوى مصفوفتان مختلفتان أبدًا باستخدام ==؛ وفي Java، استخدم Arrays.equals.

أسئلة شائعة4

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

باستخدام نافذة منزلقة، يكون التعقيد O(m + n)، حيث إن m هو طول s1 وn هو طول s2. تحسب s1 مرة واحدة، ثم يدخل كل حرف من s2 النافذة مرة واحدة ويخرج منها مرة واحدة. أما إعادة العد من البداية لكل نافذة فتكلف O(n · m) بدلًا من ذلك.

هل تعني مسألة «التبديل في سلسلة نصية» العثور على كلمة مُعاد ترتيب حروفها داخل سلسلة نصية؟

نعم. التبديل الترتيبي لـ s1 هو مقلوبٌ حرفيٌّ له، لذا فالسؤال هو ما إذا كانت هناك سلسلة فرعية من s2 بطول m تكون مقلوبًا حرفيًا لـ s1. تقارن عملية التحقق من المقلوب الحرفي بين سلسلتين كاملتين عدد مرات ظهور الأحرف مرة واحدة؛ أما هنا، فتُجرى المقارنة نفسها على نافذة تنزلق على طول s2.

لماذا تكون النافذة المنزلقة ذات حجم ثابت هنا؟

يحتوي كل تبديل لـ s1 على m أحرف بالضبط، لذا لا يمكن أن تتطابق إلا النوافذ ذات الطول m. مسائل مثل أطول سلسلة فرعية بلا أحرف مكررة تكبّر النافذة وتصغّرها؛ أما هنا فيتحرك الطرفان معًا، خطوةً واحدةً في كل مرة.

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

نعم، وستحتاج إلى واحدة إذا كان بإمكان السلاسل النصية أن تحتوي على أي محرف. إذا كانت تحتوي على أحرف صغيرة فقط، فستكون المصفوفة ذات الحجم 26 أسرع وتستخدم مساحة ثابتة. عند استخدام خريطة، احذف المفتاح عندما ينخفض عدده إلى 0 لكي تتطابق خريطتان تحتويان على الأحرف نفسها، أو استخدم العداد unbalanced من الطريقة السابقة، فهو يعمل بالطريقة نفسها مع الخريطة.

Python

def checkInclusion(s1, s2):
    # اكتب الكود هنا

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

الحالة 1

الحالة 2

الحالة 3

المدخلات

s1 = "tar"
s2 = "smartphone"

المتوقع

true

Permutation in String

الدالة

القيود

أمثلة

تلميحات

الحل

عُدَّ كل نافذة من البداية

حرّك النافذة وقارن بين 26 عددًا

حرّك النافذة وتتبّع الأحرف غير المتوازنة

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

أسئلة شائعة4

مسائل مشابهة