Coding Interview Prep · บทเรียน

ลำดับย่อยและสตริงย่อยพาลินโดรมที่ยาวที่สุด

ใช้ DP แบบช่วงเพื่อหาลำดับย่อยพาลินโดรมที่ยาวที่สุด และใช้เทคนิคขยายรอบจุดกึ่งกลางเพื่อหาสตริงย่อยพาลินโดรมที่ยาวที่สุด

ลำดับย่อยและสตริงย่อยพาลินโดรมที่ยาวที่สุด เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 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 ตามความยาวช่วงที่เพิ่มขึ้น ซึ่งเป็นรูปแบบเดียวกับ DP แบบช่วงทั่วไป สำหรับแต่ละช่วง [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'))  # 4

LPS ผ่านความเท่าเทียมกับ 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) time รวมเป็น O(n³) มีแนวทางที่เร็วกว่าอีกสองแบบ ได้แก่ DP แบบช่วงที่ใช้ O(n²) time และพื้นที่ และ การขยายรอบจุดกึ่งกลางที่ใช้ O(n²) time แต่ใช้พื้นที่ O(1) สำหรับการสัมภาษณ์ มักนิยมการขยายรอบจุดกึ่งกลาง เพราะมีค่าคงที่น้อยกว่าและมีโค้ดที่อ่านง่ายกว่า

DP แบบช่วงสำหรับสตริงย่อยแบบพาลินโดรม

กำหนดให้ 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²) time และใช้พื้นที่ 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) time จึงรวมเป็น 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

DP แบบช่วงสำหรับ 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')

การเปรียบเทียบความซับซ้อนด้าน time ของ LPS และ LCS

ทั้ง LPS ด้วย DP แบบช่วงและ LCS ใช้ O(n²) time และใช้พื้นที่ O(n²) ส่วนการขยายรอบจุดกึ่งกลางสำหรับสตริงย่อยแบบพาลินโดรมที่ยาวที่สุดใช้ O(n²) time แต่ใช้พื้นที่เพียง O(1) อัลกอริทึมมานาเคอร์แก้ปัญหาสตริงย่อยได้ใน O(n) time และใช้พื้นที่ O(n) แต่ซับซ้อนมากจนผู้สัมภาษณ์แทบไม่คาดหวังให้ใช้ สำหรับบริบทการสัมภาษณ์ส่วนใหญ่ การขยายรอบจุดกึ่งกลางคือ solution ที่เหมาะสมที่สุดตามที่คาดหวังสำหรับรูปแบบสตริงย่อย

ข้อผิดพลาดที่พบบ่อยและกรณีขอบเขต

โปรดระวังข้อผิดพลาดเหล่านี้: (1) การสับสนระหว่างลำดับย่อยกับสตริงย่อย — ทั้งสองเป็นโจทย์คนละแบบและมีวิธีแก้ต่างกัน (2) กรณีฐานของ DP แบบช่วงสำหรับช่วงที่มีความยาว 2 ต้องจัดการเป็นพิเศษ เนื่องจาก dp[i+1][j-1] จะกลายเป็น dp[i+1][i] (ช่วงว่าง) (3) สำหรับการขยายจากจุดกึ่งกลาง ให้กำหนดค่าเริ่มต้นของ max_len = 1 (อักขระเดี่ยวทุกตัวเป็นพาลินโดรม); และ (4) เมื่อดึงผลลัพธ์ออกมา ให้คำนวณ start = i - (best-1)//2 เพื่อหาดัชนีเริ่มต้นจากจุดกึ่งกลางได้อย่างถูกต้อง

ตรวจสอบอย่างรวดเร็ว

ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้

ทบทวนบทเรียน

ในบทเรียนนี้ คุณได้เรียนรู้ว่า LPS ใช้ DP แบบช่วง โดยมีสมการเวียนเกิด dp[i][j] = dp[i+1][j-1]+2 เมื่ออักขระตรงกัน, สตริงย่อยแบบพาลินโดรมที่ยาวที่สุดควรแก้ด้วยการขยายจากจุดกึ่งกลาง ซึ่งใช้เวลา O(n²) และพื้นที่ O(1) และ LPS เท่ากับ LCS ของสตริงกับสตริงที่กลับลำดับ บทถัดไปเราจะจัดการกับการแบ่งสตริงเป็นพาลินโดรม II ซึ่งผสานตารางพาลินโดรมเข้ากับ DP 1 มิติเพื่อหาจำนวนครั้งตัดที่น้อยที่สุด

คำถามที่พบบ่อย

บทเรียน “ลำดับย่อยและสตริงย่อยพาลินโดรมที่ยาวที่สุด” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “ลำดับย่อยและสตริงย่อยพาลินโดรมที่ยาวที่สุด” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “ลำดับย่อยและสตริงย่อยพาลินโดรมที่ยาวที่สุด”

ใช้ DP แบบช่วงเพื่อหาลำดับย่อยพาลินโดรมที่ยาวที่สุด และใช้เทคนิคขยายรอบจุดกึ่งกลางเพื่อหาสตริงย่อยพาลินโดรมที่ยาวที่สุด คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน

บทเรียน “ลำดับย่อยและสตริงย่อยพาลินโดรมที่ยาวที่สุด” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม

ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

รูปแบบ DP แบบช่วงและลำดับการเติมค่า
ลำดับย่อยและสตริงย่อยพาลินโดรมที่ยาวที่สุด
การแบ่งพาลินโดรม II
ระเบิดลูกโป่ง: DP แบบช่วงย้อนกลับ

← กลับไปที่ Coding Interview Prep