การแบ่งพาลินโดรม II

def build_palindrome_table(s):
    n = len(s)
    is_pal = [[False]*n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for i in range(n-1):
        is_pal[i][i+1] = (s[i] == s[i+1])
    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
    return is_pal

print(build_palindrome_table('aab'))

def min_cut(s):
    n = len(s)
    is_pal = build_palindrome_table(s)
    cuts = [float('inf')] * n
    
    for i in range(n):
        if is_pal[0][i]:
            cuts[i] = 0  # entire prefix is a palindrome
        else:
            for j in range(i):
                if is_pal[j+1][i]:
                    cuts[i] = min(cuts[i], cuts[j] + 1)
    
    return cuts[n-1]

def build_palindrome_table(s):
    n = len(s)
    is_pal = [[False]*n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for i in range(n-1):
        is_pal[i][i+1] = (s[i] == s[i+1])
    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
    return is_pal

def min_cut(s):
    n = len(s)
    is_pal = build_palindrome_table(s)
    cuts = [float('inf')] * n
    for i in range(n):
        if is_pal[0][i]:
            cuts[i] = 0
        else:
            for j in range(i):
                if is_pal[j+1][i]:
                    cuts[i] = min(cuts[i], cuts[j] + 1)
    return cuts[n-1]

print(min_cut('aab'))   # 1
print(min_cut('ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab'))

def build_pal_expand(s):
    n = len(s)
    is_pal = [[False]*n for _ in range(n)]
    
    def expand(l, r):
        while l >= 0 and r < n and s[l] == s[r]:
            is_pal[l][r] = True
            l -= 1; r += 1
    
    for i in range(n):
        expand(i, i)    # odd-length centres
        expand(i, i+1)  # even-length centres
    return is_pal

print('Expand-around-centre palindrome table built')

def partition_all(s):
    n = len(s)
    is_pal = build_pal_expand(s)
    result = []
    
    def backtrack(start, path):
        if start == n:
            result.append(path[:])
            return
        for end in range(start, n):
            if is_pal[start][end]:
                path.append(s[start:end+1])
                backtrack(end+1, path)
                path.pop()
    
    backtrack(0, [])
    return result

print(partition_all('aab'))  # [['a','a','b'], ['aa','b']]

def min_cut_clean(s):
    n = len(s)
    is_pal = build_palindrome_table(s)
    cuts = list(range(n))  # cuts[i] = i (worst case)
    
    for i in range(n):
        if is_pal[0][i]:
            cuts[i] = 0
        else:
            for j in range(1, i+1):
                if is_pal[j][i]:
                    cuts[i] = min(cuts[i], cuts[j-1] + 1)
    return cuts[n-1]

def build_palindrome_table(s):
    n = len(s)
    is_pal = [[False]*n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for i in range(n-1):
        is_pal[i][i+1] = (s[i] == s[i+1])
    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
    return is_pal

def min_cut(s):
    n = len(s)
    is_pal = build_palindrome_table(s)
    cuts = list(range(n))
    for i in range(n):
        if is_pal[0][i]:
            cuts[i] = 0
        else:
            for j in range(1, i+1):
                if is_pal[j][i]:
                    cuts[i] = min(cuts[i], cuts[j-1] + 1)
    return cuts[n-1]

print(min_cut('a'))     # 0
print(min_cut('aaaa'))  # 0
print(min_cut('abc'))   # 2