Is Subsequence
لديك سلسلتان، s وt. أعد true إذا كان بإمكانك تحويل t إلى s بحذف بعض أحرفها (أو عدم حذف أي منها) مع الحفاظ على ترتيب الأحرف المتبقية، وأعد false خلاف ذلك. على سبيل المثال، ace هي سلسلة جزئية من abcde، لكن aec ليست كذلك.
الدالة
- sstring
- السلسلة النصية المراد البحث عنها
- tstring
- السلسلة النصية التي تُحذف منها الأحرف
- تُرجعboolean
- صحيح إذا أمكن قراءة s داخل t بالترتيب، مع احتمال وجود فجوات
القيود
1 ≤ s.length ≤ 3 × 1041 ≤ t.length ≤ 5 × 104sوtيحتويان على أحرف إنجليزية صغيرة فقط.
أمثلة
- المدخلات
- s = "ace"t = "abcde"
- المخرجات
- true
- الشرح
- احذف
bوdمنabcde، فيتبقىaceبالترتيب نفسه.
- المدخلات
- s = "aec"t = "abcde"
- المخرجات
- false
- الشرح
- يحتوي
tعلى الأحرف الثلاثة، لكنcالوحيدة تقع قبلeالوحيدة. بعد استخدامeعند الفهرس 4، لا يتبقى أيcعلى يمينه.
- المدخلات
- s = "moon"t = "monsoon"
- المخرجات
- true
- الشرح
- استخدم الحرف
mعند الفهرس 0، وحرفَيoعند الفهرسين 1 و4، والحرفnعند الفهرس 6 منmonsoon. تُحذف الأحرف الواقعة بينها.
سؤال إضافي
إذا بقيت t ثابتة وفحصت مليون سلسلة s مقابلها، فكيف ستُعِدّ t بحيث يكون كل فحص أسرع من قراءة t كاملة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
انظر إلى الحرف الأول من
s. أي نسخة منه فيtينبغي أن تستخدم؟استخدم النسخة الأسبق. اختيار نسخة لاحقة لا يمكن إلا أن يترك جزءًا أقل من
tلبقيةs، لذا فإن الاختيار الأسبق ليس أسوأ أبدًا.احتفظ بفهرس في
sوآخر فيt. تحرّك عبرtحرفًا واحدًا في كل مرة، وقدّم الفهرس فيsعند كل تطابق، ثم تحقّق في النهاية مما إذا كان قد وصل إلى نهايةs.
الحل
يمكن للمتتالية الجزئية تخطي أحرف من t في أي موضع، ما يوحي بتجربة مواضع عديدة لـs. لا حاجة إلى ذلك: فمطابقة كل حرف من s في أسبق موضع يمكن أن يأتي فيه ليست أسوأ أبدًا من أي خيار آخر، لذا تكفي عملية مرور واحدة من اليسار إلى اليمين باستخدام مؤشرين لتحديد ذلك.
البرمجة الديناميكية على البادئات
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
لتكن dp[i][j] دالةً تحدد ما إذا كانت الأحرف i الأولى من s تلائم الأحرف j الأولى من t. تلائمها إذا كانت تلائمها بالفعل من دون t[j-1]، أو إذا كان s[i-1] يساوي t[j-1] وكانت الأحرف i-1 الأولى تلائم t[:j-1]. البادئة الفارغة تلائم كل شيء، والصف i لا يقرأ إلا الصف i-1، لذا يكفي صفّان طول كل منهما m+1.
يملأ الجدول كل خلية: مع s من 25,000 حرف وt من 50,000 حرف، يكون المجموع 1.25 × 10^9 خلية.
الخوارزمية
- أنشئ صفًا
prevمنm+1قيمة، جميعهاtrue: إذ يمكن أن تتطابقsالفارغة مع كل بادئة منt. - لكل
iمن 1 إلىn، أنشئ صفًاcurمعcur[0] = false. - لكل
jمن 1 إلىm، اجعلcur[j]مساويًا لـcur[j-1]، أو لـprev[j-1]عندما تكونs[i-1]مساوية لـt[j-1]. - استبدل
prevبـcur. - أعِد
prev[m].
def isSubsequence(s, t):
n, m = len(s), len(t)
# prev[j]: the first i-1 letters of s fit inside t[:j]. An empty s fits anywhere.
prev = [True] * (m + 1)
for i in range(1, n + 1):
cur = [False] * (m + 1)
for j in range(1, m + 1):
cur[j] = cur[j - 1] or (s[i - 1] == t[j - 1] and prev[j - 1])
prev = cur
return prev[m]مؤشّران مع المطابقة الجشعة
الفكرة
احتفظ بمؤشر i يشير إلى الحرف التالي من s الذي تحتاج إليه، وخذ أول نسخة منه تصادفها في t. هذا الاختيار آمن. إذا كان هناك موضع صالح يستخدم نسخة لاحقة من s[i]، فإن استبدالها بأول نسخة يحافظ على الترتيب ويُبقي جزءًا أكبر من t لبقية أحرف s. لذا، إذا وُجد أي موضع صالح، فستعثر عليه الطريقة الجشعة.
تقرأ الحلقة كل حرف من t مرة واحدة على الأكثر، وتحتفظ بمؤشرين: زمن O(n + m) وذاكرة O(1).
الخوارزمية
- عيّن
i = 0لـsوj = 0لـt. - ما دام كلا الفهرسين داخل سلسلتيهما، فقارن
s[i]بـt[j]. - إذا كانا متساويين، فزِد
i. - زِد
jفي كل الحالات. - أعِد ما إذا كان
iيساوي طولs.
def isSubsequence(s, t):
i = j = 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)
أخطاء شائعة وحالات حدّية
- البحث عن كل حرف من
sفي أي موضع داخلtبدلًا من البحث بعد الموضع الذي عُثر فيه على الحرف السابق. هذا يقبلaecفيabcde. - استخدام نسخة واحدة من حرف مرتين.
noonليست سلسلة جزئية منmoon: لا يمكن أن يكون حرفnالوحيد فيها، عند الفهرس 3، الحرف الأول والأخير في الوقت نفسه. - إرجاع ما إذا كان
jقد وصل إلى نهايةt. غالبًا ما تنتهي الحلقة عندها سواء عُثر علىsأم لا؛ وحدهiيخبرك بذلك. - عدم التوقف عند نفاد أحرف
t. يجب أن تُرجع مقارنةabcمعabالقيمةfalse. - قراءة
s[i]بعد وصولiإلى نهايةs. في Python أو Java، تؤدي هذه القراءة إلى استثناء، لذا تحقّق منiقبل المقارنة.
أسئلة شائعة3
ما هو التعقيد الزمني لمسألة التحقق مما إذا كانت سلسلة فرعية؟
يعمل حل المؤشرين في زمن O(n + m)، حيث يمثّل n وm طولَي s وt، مع ذاكرة إضافية مقدارها O(1). تتوقف الحلقة بعد m خطوات كحد أقصى. يستغرق جدول البادئات زمنًا قدره O(n × m).
ما علاقة مسألة «هل هي تتابع جزئي» بأطول تتابع مشترك؟
يكون s تسلسلًا جزئيًا من t بالضبط عندما يكون طول أطول تسلسل مشترك بينهما n، أي طول s بالكامل. جدول البادئات في النهج الأول هو الجدول الذي تبنيه لهذه المسألة. هنا تحتاج فقط إلى معرفة ما إذا كان s بالكامل يلائم، لذا تكفي عملية المرور الجشعة.
ما الفرق بين المتتالية الجزئية والسلسلة الجزئية؟
السلسلة الفرعية هي مجموعة من الأحرف المتتالية، بينما يمكن أن تتخطى السلسلة الجزئية بعض الأحرف ما دام ترتيب الأحرف كما هو. ace سلسلة جزئية من abcde لكنها ليست سلسلة فرعية منه. كل سلسلة فرعية هي سلسلة جزئية، لكن العكس ليس صحيحًا.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def isSubsequence(s, t):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
s = "ace" t = "abcde"
الإخراج المتوقع
true