مختبر بايثون التفاعلي

Longest Common Subsequence

يعمل الـ Playground تلقائياً عند التحميل. انقر على شغّل الكود لتتبع كود بايثون الخاص بك — كل خطوة بالرسوم المتحركة مباشرة.

اشرح·سطر بسطر

إعادة تشغيل·خطوة بخطوة

تحدي·تلميحات موجهة

XP·...

خط أنابيب تدفق البيانات

mastery المسار

Dijkstra's Shortest Path

0/1 Knapsack DP

Longest Common Subsequence

Coin Change DP

Topological Sort (Kahn's)

Kruskal's MST

Trie (Prefix Tree)

Floyd-Warshall All-Pairs Shortest Path

Segment Tree for Range Queries

Bit Manipulation Tricks

اشرح

Line 1

lcs('ABCBDAB', 'BDCAB') called. m=7, n=5.

لماذا هذا النهج؟

We want the longest subsequence present in both strings. A subsequence doesn't need to be contiguous. BDAB is common with length 4.

التعقيد

الوقت

O(m × n)

المساحة

O(m × n)

نظرة عامة على التعقيد

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

n = 8النطاق 1-20

عند N = 8

التعقيد	العمليات
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

تحدي

Try lcs('AGGTAB', 'GXTXAYB'). What is the LCS length? Which characters form it?

تلميح

We build a 2D matrix comparing character to character. Diagonal progression tracks the matching backbone.

استوديو الكود

Longest Common Subsequence

Monaco جاهز

بايثون جاهز

lesson.pyline 1

Loading editor...

وحدة الإخراج

1 lines

❯ 4

تطبيقات العالم الحقيقي

1

The engine underneath `git diff`

2

DNA / Genomic sequencing

3

Levenshtein autocorrect bases

Comments

Loading comments...