Belajar Algoritm - DP on Strings

#Pendahuluan

Setelah di episode 15 kita membahas tiga masalah DP klasik — Knapsack, LCS, dan Edit Distance — pada episode ini kita memperdalam DP on strings: masalah di mana state DP merepresentasikan substring atau prefix/suffix dari string. Pola ini berbeda dari DP on arrays karena kita harus mempertimbangkan posisi awal dan akhir substring, atau perbandingan antara dua string.

DP on strings adalah fondasi untuk text processing — dari pencarian pola, analisis DNA, hingga NLP modern. Memahami pola ini akan membantu kalian menyelesaikan berbagai masalah string yang muncul di interview dan production.

#Pola State: dp[i][j]

Untuk DP on strings, ada dua pendekatan state utama:

dp[i][j] = solusi untuk substring s[i..j] — digunakan untuk masalah palindromic, substring problems. Iterasi: panjang substring dari 1 ke n.

dp[i][j] = solusi untuk prefix s[0..i-1] dan t[0..j-1] — digunakan untuk masalah perbandingan dua string (LCS, edit distance). Iterasi: i dari 0 ke m, j dari 0 ke n.

#Longest Palindromic Subsequence

LPS: panjang subsequence terpanjang yang merupakan palindrom dari string s. Berbeda dari longest palindromic substring (kontigu), LPS memungkinkan karakter terpisah.

python

def longest_palindromic_subsequence(s):
    n = len(s)
    # dp[i][j] = LPS dari s[i..j]
    dp = [[0] * n for _ in range(n)]
    
    # Base case: satu karakter selalu palindrom
    for i in range(n):
        dp[i][i] = 1
    
    # Isi untuk panjang substring 2 ke n
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    
    return dp[0][n-1]

Transition: jika s[i] == s[j], LPS = LPS(i+1, j-1) + 2. Jika tidak, LPS = max(LPS(i+1, j), LPS(i, j-1)).

Koneksi ke LCS: LPS(s) = LCS(s, reverse(s)). Ini memberikan alternatif implementasi.

#Word Break

Word Break: apakah string s bisa dipecah menjadi sekumpulan kata dari dictionary? Contoh: "leetcode" bisa dipecah menjadi ["leet", "code"].

python

def word_break(s, word_dict):
    n = len(s)
    word_set = set(word_dict)
    dp = [False] * (n + 1)
    dp[0] = True  # string kosong selalu bisa di-break
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    
    return dp[n]

Transition: dp[i] = True jika ada j di mana dp[j] == True DAN s[j..i] ada di dictionary.

Optimasi: batasi panjang kata yang diperiksa berdasarkan panjang kata terpanjang di dictionary. Ini mengurangi inner loop dari O(n) ke O(max_word_length).

Note

Word break adalah contoh di mana DP 1D (bukan 2D) sudah cukup — state hanya bergantung pada posisi awal i, bukan pasangan (i, j). Kunci: identifikasi apakah masalah membutuhkan dua indeks atau satu.

#Wildcard Matching

Wildcard Matching: cocokkan string s dengan pola p yang mengandung ? (cocok satu karakter) dan * (cocok zero atau lebih karakter).

python

def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    
    # Pola kosong hanya cocok dengan string kosong
    # Namun, '*' bisa "menyerap" prefix kosong
    for j in range(1, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-1]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '*':
                # '*' cocok dengan zero karakter (dp[i][j-1])
                # atau satu+ karakter (dp[i-1][j])
                dp[i][j] = dp[i][j-1] or dp[i-1][j]
            elif p[j-1] == '?' or s[i-1] == p[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = False
    
    return dp[m][n]

Transisi untuk *: dp[i][j] = dp[i][j-1] (zero karakter) ATAU dp[i-1][j] (satu+ karakter). Ini menangani * yang bisa "menyerap" jumlah karakter berapa pun.

#Tips Umum DP on Strings

Pola	State	Kapan
Substring s[i..j]	dp[i][j]	Masalah palindromic, substring
Perbandingan dua string	dp[i][j] = prefix s[0..i], t[0..j]	LCS, edit distance, wildcard
Split/exist in dict	dp[i] = prefix s[0..i]	Word break, palindrome partition

Tip

Ketika menghadapi masalah string DP, tanyakan: "Apakah saya perlu mempertimbangkan substring s[i..j] atau prefix s[0..i]?" Jika iya → 2D. Jika hanya satu string dan posisi → 1D.

#Penutup

Pada episode 16 ini, kalian telah memahami:

dp[i][j] untuk substring s[i..j]: longest palindromic subsequence, palindrome problems.
dp[i][j] untuk prefix: wildcard matching, perbandingan dua string.
dp[i] untuk prefix s[0..i]: word break, single-string problems.
Koneksi LPS ke LCS: LPS(s) = LCS(s, reverse(s)).

Di episode 17 selanjutnya kita akan membahas DP on Trees & Graphs — diameter of tree, house robber III, shortest path di DAG, dan matrix chain multiplication. Sampai jumpa di episode 17!