ลำดับร่วมที่ยาวที่สุด

ลำดับย่อยคืออะไร

# Subsequence vs Substring
# 'ACE' is a subsequence of 'ABCDE' (skip B, D)
# 'ACE' is NOT a substring of 'ABCDE' (must be contiguous)

# LCS examples:
# LCS('ABCBDAB', 'BDCABA') = 4 ('BCBA' or 'BDAB')
# LCS('AGGTAB', 'GXTXAYB') = 4 ('GTAB')
# LCS('ABC', 'AC') = 2 ('AC')

print('Subsequence check: ACE in ABCDE')
text = 'ABCDE'
pattern = 'ACE'
i = 0
for ch in text:
    if i < len(pattern) and ch == pattern[i]: i += 1
print('Found:', i == len(pattern))  # True

การอนุมานความสัมพันธ์เวียนเกิดของ LCS

def lcs_length(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1  # extend match
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # skip one
    return dp[m][n]

print(lcs_length('ABCBDAB', 'BDCABA'))  # 4
print(lcs_length('AGGTAB', 'GXTXAYB')) # 4
print(lcs_length('ABC', 'AC'))         # 2

การติดตามตาราง LCS

def lcs_trace(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    # Print table
    print('   ', ' '.join(text2))
    for i, row in enumerate(dp):
        label = ' ' if i == 0 else text1[i-1]
        print(label, row)
    return dp[m][n]

lcs_trace('ABCD', 'ACBD')

การสร้าง LCS จริงกลับคืน

def lcs_reconstruct(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    # Backtrack
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if text1[i-1] == text2[j-1]:
            result.append(text1[i-1])
            i -= 1; j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(result))

print(lcs_reconstruct('ABCBDAB', 'BDCABA'))  # BCBA or BDAB

การลดการใช้พื้นที่เหลือ O(n)

def lcs_o1_space(text1, text2):
    m, n = len(text1), len(text2)
    dp = [0] * (n + 1)  # represents previous row
    for i in range(1, m + 1):
        diag = 0  # dp[i-1][j-1]
        for j in range(1, n + 1):
            temp = dp[j]  # save current (will become diagonal for next j)
            if text1[i-1] == text2[j-1]:
                dp[j] = diag + 1
            else:
                dp[j] = max(dp[j], dp[j-1])
            diag = temp
    return dp[n]

print(lcs_o1_space('ABCBDAB', 'BDCABA'))  # 4
print(lcs_o1_space('AGGTAB', 'GXTXAYB')) # 4

ความสัมพันธ์ระหว่าง LCS กับระยะห่างการแก้ไข

def lcs_length(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[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]

def min_edits_insert_delete(s1, s2):
    lcs = lcs_length(s1, s2)
    return len(s1) + len(s2) - 2 * lcs

print(min_edits_insert_delete('ABCD', 'ANCD'))  # 2 (delete B, insert N)
print(min_edits_insert_delete('horse', 'ros'))   # 5

การลบเพื่อทำให้สตริงสองชุดเท่ากัน

def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    lcs = dp[m][n]
    return m + n - 2 * lcs  # deletions needed

print(min_distance('sea', 'eat'))  # 2 (delete s, delete t)
print(min_distance('leetcode', 'etco'))  # 4

สตริงย่อยร่วมที่ยาวที่สุด

def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    max_len = 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                max_len = max(max_len, dp[i][j])
            # else dp[i][j] stays 0 (reset)
    return max_len

# LCS (subseq) vs substring:
print('LCS subseq:', lcs_length('ABCBDAB', 'BDCABA'))        # 4 (BCBA)
print('LCS substring:', longest_common_substring('ABCBDAB', 'BDCABA'))  # 2 (BD or AB)

LCS สำหรับการเปรียบเทียบลำดับ

def diff(old_lines, new_lines):
    '''Simple diff using LCS to find unchanged lines.'''
    m, n = len(old_lines), len(new_lines)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if old_lines[i-1]==new_lines[j-1]: dp[i][j]=dp[i-1][j-1]+1
            else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    # Backtrack to produce diff
    output, i, j = [], m, n
    while i>0 or j>0:
        if i>0 and j>0 and old_lines[i-1]==new_lines[j-1]:
            output.append('  '+old_lines[i-1]); i-=1; j-=1
        elif j>0 and (i==0 or dp[i][j-1]>=dp[i-1][j]):
            output.append('+ '+new_lines[j-1]); j-=1
        else:
            output.append('- '+old_lines[i-1]); i-=1
    return list(reversed(output))

for line in diff(['a','b','c'], ['a','x','c']): print(line)

ลำดับเหนือร่วมที่สั้นที่สุด

def shortest_common_supersequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1
            else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    # Reconstruct
    result, i, j = [], m, n
    while i>0 and j>0:
        if s1[i-1]==s2[j-1]: result.append(s1[i-1]); i-=1; j-=1
        elif dp[i-1][j]>dp[i][j-1]: result.append(s1[i-1]); i-=1
        else: result.append(s2[j-1]); j-=1
    while i>0: result.append(s1[i-1]); i-=1
    while j>0: result.append(s2[j-1]); j-=1
    return ''.join(reversed(result))

print(shortest_common_supersequence('abac', 'cab'))  # 'cabac' length 5

ความซับซ้อนของ LCS และเคล็ดลับการสัมภาษณ์

# LCS: O(mn) time, O(min(m,n)) space with rolling array
# Longest Increasing Subsequence (related but 1D):
from bisect import bisect_left

def lis_length(nums):
    '''Patience sorting: O(n log n) LIS length.'''
    tails = []
    for num in nums:
        pos = bisect_left(tails, num)
        if pos == len(tails): tails.append(num)
        else: tails[pos] = num
    return len(tails)

print(lis_length([10, 9, 2, 5, 3, 7, 101, 18]))  # 4 (2,3,7,101 or 2,5,7,18)

ตรวจสอบความเข้าใจ

สรุปบทเรียน