أطول تتابع جزئي وسلسلة فرعية متناظرة
طبّق البرمجة الديناميكية للفواصل للعثور على أطول تتابع جزئي متناظر، واستخدم حيلة التوسّع حول المركز للعثور على أطول سلسلة فرعية متناظرة.
أطول تتابع جزئي وسلسلة فرعية متناظرة درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
إعادة النظر في تعريفات المتناظرات
إن المتتالية الجزئية المتناظرة هي متتالية جزئية (لا يشترط أن تكون عناصرها متجاورة) تُقرأ بالطريقة نفسها من الأمام والخلف. أما السلسلة الفرعية المتناظرة فتشترط أن تكون الأحرف متجاورة. بالنسبة إلى 'bbbab'، فإن أطول متتالية جزئية متناظرة هي 'bbbb' (بطول 4)، بينما أطول سلسلة فرعية متناظرة هي 'bbb' (بطول 3). تتطلب المسألتان تقنيتين مختلفتين رغم تشابه اسميهما.
أطول متتالية جزئية متناظرة: حالة LPS
عرّفوا dp[i][j] على أنه طول أطول متتالية جزئية متناظرة في s[i..j]. تكون علاقة التكرار كما يلي: إذا كان s[i] == s[j]، فإن dp[i][j] = dp[i+1][j-1] + 2 (إذ يوسّع الحرفان المتطابقان المتناظرة الداخلية). وإلا فإن dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (تجاوز الحرف الأيسر أو الأيمن). الحالة الأساسية: dp[i][i] = 1 لجميع الأحرف المفردة.
s = 'bbbab'
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
print('Base cases set, dp[i][i] = 1 for all i')ترتيب ملء LPS وتنفيذه
نملأ جدول LPS وفق أطوال الفترات المتزايدة، باتباع النمط نفسه المستخدم في البرمجة الديناميكية العامة على الفترات. لكل فترة [i, j] طولها 2 أو أكثر، نتحقق مما إذا كان الحرفان عند الطرفين متطابقين، ثم نطبّق علاقة التكرار. تكون الإجابة النهائية هي dp[0][n-1]، أي LPS للسلسلة بأكملها.
def longest_palindromic_subsequence(s):
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
inner = dp[i+1][j-1] if length > 2 else 0
dp[i][j] = inner + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
print(longest_palindromic_subsequence('bbbab')) # 4LPS من خلال تكافؤ LCS
يوجد بديل أنيق: قيمة LPS للسلسلة s تساوي قيمة LCS للسلسلة s ومعكوسها s[::-1]. يعود ذلك إلى أن أي متتالية جزئية متناظرة في s هي متتالية جزئية مشتركة بين s ومعكوسها. يتيح لكم هذا الاختزال إعادة استخدام شفرة LCS مباشرة. فعند عكس 'bbbab' نحصل على 'babbb'، وتبلغ قيمة LCS بينهما 4.
def lps_via_lcs(s):
t = s[::-1]
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lps_via_lcs('bbbab')) # 4أطول سلسلة فرعية متناظرة: القوة الغاشمة
تتطلب أطول سلسلة فرعية متناظرة أحرفًا متجاورة. يتحقق أسلوب القوة الغاشمة من جميع السلاسل الفرعية وعددها O(n²)، ويفحص كل واحدة منها في زمن O(n)، أي بزمن إجمالي O(n³). يوجد أسلوبان أسرع: البرمجة الديناميكية على الفترات بزمن ومساحة O(n²)، والتوسّع حول المركز بزمن O(n²) ومساحة O(1). في المقابلات، يُفضَّل التوسّع حول المركز لأنه يتطلب ثابتًا أصغر وشفرة أوضح.
البرمجة الديناميكية على الفترات للسلسلة الفرعية المتناظرة
عرّفوا dp[i][j] = True إذا كانت s[i..j] متناظرة. علاقة التكرار: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. الحالات الأساسية: dp[i][i] = True وdp[i][i+1] = (s[i] == s[i+1]). تتبّعوا المتناظرة ذات الطول الأكبر التي عُثر عليها. املؤوا الجدول وفق ترتيب الأطوال المتزايدة. يعمل هذا الحل بزمن O(n²) ومساحة O(n²).
def longest_palindrome_dp(s):
n = len(s)
dp = [[False]*n for _ in range(n)]
start, max_len = 0, 1
for i in range(n):
dp[i][i] = True
for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
start, max_len = i, 2
for length in range(3, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
if length > max_len:
start, max_len = i, length
return s[start:start+max_len]
print(longest_palindrome_dp('babad')) # 'bab' or 'aba'تقنية التوسّع حول المركز
تجرّب طريقة التوسّع حول المركز كل حرف (وكل زوج من الأحرف المتجاورة) بوصفه مركزًا محتملًا لمتناظرة، ثم تتوسّع إلى الخارج ما دام الطرفان متطابقين. يوجد 2n-1 مركزًا محتملًا (n مركزًا للمتناظرات ذات الطول الفردي، وn-1 للمتناظرات ذات الطول الزوجي). يستغرق كل توسّع زمنًا لا يتجاوز O(n)، ما يعطي زمنًا إجماليًا قدره O(n²) مع مساحة O(1)، وهو الحل الأمثل لمعظم المقابلات.
def longest_palindrome_expand(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l - 1 # length of palindrome
start, max_len = 0, 1
for i in range(len(s)):
odd = expand(i, i) # odd-length
even = expand(i, i+1) # even-length
best = max(odd, even)
if best > max_len:
max_len = best
start = i - (best - 1) // 2
return s[start:start+max_len]
print(longest_palindrome_expand('cbbd')) # 'bb'تحسين مساحة LPS
تستخدم البرمجة الديناميكية على الفترات لحساب LPS مساحة قدرها O(n²). عندما تحتاجون إلى الطول فقط (وليس المتتالية الجزئية نفسها)، يمكنكم تقليل المساحة من خلال ملاحظة أن dp[i][j] يعتمد فقط على dp[i+1][j-1] وdp[i+1][j] وdp[i][j-1]. ومن خلال إعادة استخدام الصفوف وحفظ قيمة قطرية واحدة، يمكنكم الوصول إلى مساحة O(n)، رغم أن التنفيذ يصبح أكثر تعقيدًا ونادرًا ما يُطلب في المقابلات.
إعادة بناء LPS
لإعادة بناء المتتالية الجزئية المتناظرة نفسها، تتبّعوا جدول DP إلى الخلف. ابدأوا من (0, n-1). إذا كان s[i] == s[j]، فأضيفوا ذلك الحرف إلى طرفي النتيجة وانتقلوا إلى (i+1, j-1). وإلا فانتقلوا إلى إحدى الحالتين (i+1, j) أو (i, j-1)، أيهما تحتوي على القيمة الأكبر. يعيد هذا التتبّع الجشع إلى الخلف إحدى المتتاليات الجزئية المتناظرة المثلى بشكل فريد.
def reconstruct_lps(s, dp):
result = []
i, j = 0, len(s) - 1
while i < j:
if s[i] == s[j]:
result.append(s[i])
i += 1; j -= 1
elif dp[i+1][j] > dp[i][j-1]:
i += 1
else:
j -= 1
# middle character for odd-length
mid = [s[i]] if i == j else []
return ''.join(result + mid + result[::-1])
print('Traceback recovers one optimal LPS')مقارنة التعقيد الزمني لـ LPS وLCS
تعمل كل من LPS باستخدام البرمجة الديناميكية على الفترات وLCS بزمن O(n²) ومساحة O(n²). أما التوسّع حول المركز لإيجاد أطول سلسلة فرعية متناظرة فيستغرق زمن O(n²)، لكنه يحتاج إلى مساحة O(1) فقط. تحل خوارزمية Manacher مسألة السلسلة الفرعية بزمن ومساحة O(n)، لكنها معقدة إلى حد لا يتوقع معه المحاورون استخدامها غالبًا. وفي معظم سياقات المقابلات، يُعد التوسّع حول المركز الحل الأمثل المتوقع لنسخة السلسلة الفرعية.
الأخطاء الشائعة والحالات الحدّية
انتبهوا إلى الأخطاء التالية: (1) الخلط بين التتابع الجزئي والسلسلة الفرعية — فهما مسألتان مختلفتان ولهما حلّان مختلفان؛ (2) تحتاج الحالة الأساسية في البرمجة الديناميكية على الفواصل للفواصل ذات الطول 2 إلى معالجة خاصة، لأن dp[i+1][j-1] ستصبح dp[i+1][i] (فاصلًا فارغًا)؛ (3) في التوسّع حول المركز، ابدؤوا بـ max_len = 1 (كل محرف منفرد يمثل سلسلة متناظرة)؛ و(4) عند استخراج النتيجة، احسبوا start = i - (best-1)//2 للعثور على فهرس البداية الصحيح انطلاقًا من المركز.
تحقق سريع
اختبروا مدى فهمكم لمفاهيم Data Structures & Algorithms — Coding Interview Prep التي تناولها هذا الدرس.
مراجعة الدرس
تعلمتم في هذا الدرس أن: LPS يستخدم البرمجة الديناميكية على الفواصل، مع العلاقة التكرارية dp[i][j] = dp[i+1][j-1]+2 عندما تتطابق المحارف، وأن إيجاد أطول سلسلة فرعية متناظرة يُحلّ بأفضل صورة باستخدام التوسّع حول المركز بزمن O(n²) ومساحة O(1)، وأن LPS يساوي LCS للسلسلة ومعكوسها. سنتناول بعد ذلك المسألة الثانية لتقسيم السلسلة المتناظرة، التي تجمع بين جدول للسلاسل المتناظرة وبرمجة ديناميكية أحادية البعد لإيجاد الحد الأدنى من عمليات القطع.
الأسئلة الشائعة
هل درس «أطول تتابع جزئي وسلسلة فرعية متناظرة» مجاني؟
نعم — نص درس «أطول تتابع جزئي وسلسلة فرعية متناظرة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «أطول تتابع جزئي وسلسلة فرعية متناظرة»؟
طبّق البرمجة الديناميكية للفواصل للعثور على أطول تتابع جزئي متناظر، واستخدم حيلة التوسّع حول المركز للعثور على أطول سلسلة فرعية متناظرة. تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «أطول تتابع جزئي وسلسلة فرعية متناظرة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- نمط البرمجة الديناميكية للفواصل وترتيب الملء
- أطول تتابع جزئي وسلسلة فرعية متناظرة
- تقسيم السلسلة إلى مقاطع متناظرة II
- تفجير البالونات: البرمجة الديناميكية العكسية للفواصل