Permutation in String
تستخدم تبديلة السلسلة الحروف نفسها بأي ترتيب، ويظهر كل حرف فيها بعدد مرات ظهوره في السلسلة الأصلية: tar وrat وart تبديلات بعضها لبعض. لديك سلسلتان s1 وs2 مكوّنتان من أحرف إنجليزية صغيرة. أعد true إذا ظهرت أي تبديلة من s1 في s2 كسلسلة فرعية (تتابع من الأحرف المتجاورة)، وأعد false خلاف ذلك.
الدالة
- s1string
- الحروف المطلوب إعادة ترتيبها
- s2string
- السلسلة النصية التي سيتم البحث فيها
- تُرجعboolean
- صحيح إذا كانت سلسلة فرعية من s2 إعادة ترتيب لـ s1
القيود
1 ≤ s1.length ≤ 2 × 1041 ≤ s2.length ≤ 5 × 104s1و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 أحرف فقط، لذا لا يمكن أن يحتوي على ترتيبٍ منها.
سؤال إضافي
هل يمكنك إرجاع جميع الفهارس في s2 التي يبدأ عندها تبديل لـ s1، مع الحفاظ على زمن O(m + n)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
في التبديل، لا يهم ترتيب الأحرف. ما الذي يحدد ما إذا كانت سلسلة فرعية من
s2تبديلًا لـs1، وما الطول الذي يجب أن تكون عليه؟لا يمكن أن تنجح إلا السلاسل الفرعية التي يبلغ طولها
m = s1.length، وتكون هذه السلسلة الفرعية تبديلًا لـs1فقط عندما تتساوى أعداد حروفها الـ26 مع أعداد حروفs1.حرّك نافذة بطول
mعبرs2. في كل خطوة، أضف حرفًا واحدًا من اليمين وأزِل حرفًا من اليسار، لذا حدّث تكرارات الأحرف في النافذة بإضافة 1 وطرح 1 بدلًا من إعادة عدّها، ثم قارِنها بتكرارات الأحرف فيs1.
الحل
إن سرد جميع تبديلات 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.
أسئلة شائعة3
ما هو التعقيد الزمني لمسألة التبديل في السلسلة؟
باستخدام نافذة منزلقة، يكون التعقيد O(m + n)، حيث إن m هو طول s1 وn هو طول s2. تحسب s1 مرة واحدة، ثم يدخل كل حرف من s2 النافذة مرة واحدة ويخرج منها مرة واحدة. أما إعادة العد من البداية لكل نافذة فتكلف O(n · m) بدلًا من ذلك.
هل تعني مسألة «التبديل في سلسلة نصية» العثور على كلمة مُعاد ترتيب حروفها داخل سلسلة نصية؟
نعم. التبديل الترتيبي لـ s1 هو مقلوبٌ حرفيٌّ له، لذا فالسؤال هو ما إذا كانت هناك سلسلة فرعية من s2 بطول m تكون مقلوبًا حرفيًا لـ s1. تقارن عملية التحقق من المقلوب الحرفي بين سلسلتين كاملتين عدد مرات ظهور الأحرف مرة واحدة؛ أما هنا، فتُجرى المقارنة نفسها على نافذة تنزلق على طول s2.
لماذا تكون النافذة المنزلقة ذات حجم ثابت هنا؟
يحتوي كل تبديل لـ s1 على m أحرف بالضبط، لذا لا يمكن أن تتطابق إلا النوافذ ذات الطول m. مسائل مثل أطول سلسلة فرعية بلا أحرف مكررة تكبّر النافذة وتصغّرها؛ أما هنا فيتحرك الطرفان معًا، خطوةً واحدةً في كل مرة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def checkInclusion(s1, s2):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
s1 = "tar" s2 = "smartphone"
الإخراج المتوقع
true