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. تُحذف الأحرف الواقعة بينها.
+20 اختبارات مخفية عند الإرسال
سؤال إضافي
لنفترض أن t يبقى كما هو، وأن عليك التحقق من مليون سلسلة مختلفة s بمقارنته بها. كيف ستُعِدّ t بحيث يكون كل تحقق أسرع من قراءة t بالكامل من جديد؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
انظر إلى الحرف الأول من
s. أي نسخة منه فيtينبغي أن تستخدم؟استخدم أول نسخة. إن أخذ نسخة لاحقة لا يمكن إلا أن يترك قدرًا أقل من
tلبقيةs، لذا فإن اختيار النسخة الأولى ليس أسوأ أبدًا.احتفِظ بمؤشر واحد داخل
sوآخر داخلt. تقدّم فيtحرفًا واحدًا في كل مرة، وحرّك المؤشر داخلsعند كل تطابق، ثم تحقّق في النهاية مما إذا كان قد وصل إلى نهايةs.
الحل
يمكن للتتابع الجزئي أن يتخطى أحرفًا من t في أي موضع، لذا قد يبدو أن عليك تجربة طرق كثيرة لوضع s داخل t. لكنك لست بحاجة إلى ذلك. إن مطابقة كل حرف من s في أقرب موضع ممكن لا تكون أسوأ من أي خيار آخر، وهذا يحوّل البحث إلى مرور واحد من اليسار إلى اليمين باستخدام مؤشرين.
البرمجة الديناميكية على البوادئ
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
اطرح سؤالًا أصغر: هل يمكن أن تتسع الأحرف i الأولى من s ضمن الأحرف j الأولى من t؟ سمِّ الإجابة dp[i][j]. إذا اتسعت ضمن t[:j-1]، فستتسع ضمن t[:j] أيضًا، إذ يمكنك حذف t[j-1]. وإذا كان s[i-1] يساوي t[j-1]، فيمكنك استخدام هذا الحرف أيضًا، وعندها يجب أن تتسع الأحرف i-1 الأولى من s ضمن t[:j-1]. لذا dp[i][j] = dp[i][j-1] or (s[i-1] == t[j-1] and dp[i-1][j-1])، والبادئة الفارغة من s تتسع في أي موضع.
لا يقرأ الصف 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]مؤشران مع المطابقة الجشعة
الفكرة
اقرأ t من اليسار إلى اليمين، واحتفظ بمؤشر i يشير إلى الحرف التالي من s الذي لا يزال عليك إيجاده. عندما يساوي t[j] s[i]، استخدمه وحرّك i إلى الأمام. وفي كلتا الحالتين، حرّك j إلى الأمام. إذا وصل i إلى نهاية s، فهذا يعني أن كل حرف وجد موضعًا بالترتيب.
لماذا يكون اختيار أول تطابق آمنًا؟ لنفترض أن موضعًا صالحًا يستخدم نسخة لاحقة من s[i]. استبدالها بأول نسخة يُبقي الترتيب كما هو، ويترك جزءًا أكبر من t إلى اليمين لبقية s، لذا لا يفوّت الاختيار الجشع أي موضع موجود. بالنسبة إلى moon في monsoon، يأخذ المؤشر الحرف o عند الفهرس 1، ويتجاوز n وs، ثم يأخذ الحرف o عند الفهرس 4، وينتهي عند الحرف n عند الفهرس 6.
يزور j كل حرف من t مرة واحدة، ولا يتحرك i إلا إلى الأمام، لذا تتكرر الحلقة بحد أقصى m مرة. ولا يحتاج ذلك إلا إلى فهرسين في الذاكرة.
الخوارزمية
- عيّن
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: تحتويmoonعلى حرفnواحد، عند الفهرس 3، ولا يمكن أن يكون الحرف الأول والأخير فيnoonمعًا. - إرجاع ما إذا كان
jقد وصل إلى نهايةt. غالبًا ما تنتهي الحلقة عندها سواء عُثر علىsأم لا؛ وحدهiيخبرك بذلك. - نسيان أن
sقد تكون أطول منt. يجب أن تعيد المقارنة بينabcوabالقيمةfalse، وهو ما تفعله الحلقة ما دامت تتوقف عند نفادt. - قراءة
s[i]بعد وصولiإلى نهايةs. في Python أو Java، تؤدي هذه القراءة إلى استثناء، لذا تحقّق منiقبل المقارنة.
أسئلة شائعة4
ما التعقيد الزمني لمسألة «هل هي متتالية فرعية؟»؟
يعمل حل المؤشرين في زمن O(n + m)، حيث إن n وm هما طولَا s وt، ويستخدم ذاكرة إضافية قدرها O(1). عمليًا، تتوقف الحلقة بعد m خطوات كحد أقصى. يستغرق جدول البادئات زمنًا قدره O(n × m).
لماذا تنجح طريقة المؤشرين الجشعة في مسألة «هل هي متتالية فرعية»؟
إن مطابقة حرف من s في أبكر موضع ممكن له في t تترك أطول جزء ممكن من t للأحرف المتبقية. ويمكن تغيير أي موضع يستخدم نسخة لاحقة ليستخدم النسخة الأسبق دون الإخلال بالترتيب، لذا إذا وُجد أي موضع يحقق المطابقة، فستجده الطريقة الجشعة.
كيف تتحقق بسرعة من سلاسل نصية كثيرة باستخدام التعبير النمطي نفسه؟
جهّز t مرة واحدة: لكل حرف، خزّن القائمة المرتبة للفهارس التي يظهر فيها. لوضع s[i]، ابحث ثنائيًا في قائمة ذلك الحرف عن أول فهرس يلي المطابقة السابقة. تصبح تكلفة كل عملية تحقق عندئذٍ O(n log m) بدلًا من O(m).
ما الفرق بين التتابع الجزئي والسلسلة الفرعية؟
السلسلة الفرعية هي مجموعة من الأحرف المتتالية، بينما يمكن للسلسلة الجزئية تخطي بعض الأحرف ما دام ترتيب الأحرف كما هو. ace سلسلة جزئية من abcde، لكنها ليست سلسلة فرعية منه. كل سلسلة فرعية هي سلسلة جزئية، لكن العكس ليس صحيحًا.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def isSubsequence(s, t):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
s = "ace" t = "abcde"
المتوقع
true