文字列のエンコード、反転、回文

文字列をインプレースで反転する

def reverse_string(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left  += 1
        right -= 1
    return ''.join(chars)

print(reverse_string('hello'))   # 'olleh'
print(reverse_string('Hannah'))  # 'hannaH'

# Pythonic shortcut (creates new string):
print('hello'[::-1])  # 'olleh'

文中の単語の順序を反転する

def reverse_words(s):
    words = s.split()       # split and strip whitespace
    words.reverse()         # in-place reverse
    return ' '.join(words)  # single space between words

print(reverse_words('  hello   world  '))  # 'world hello'
print(reverse_words('a good example'))     # 'example good a'

# One-liner:
print(' '.join('  hello   world  '.split()[::-1]))

回文判定：基本

def is_palindrome(s):
    # Filter and normalise
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    return cleaned == cleaned[::-1]

print(is_palindrome('A man, a plan, a canal: Panama'))  # True
print(is_palindrome('race a car'))                       # False
print(is_palindrome('Was it a car or a cat I saw?'))     # True

回文判定：2ポインタ

def is_palindrome_twoptr(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1; right -= 1
    return True

print(is_palindrome_twoptr('A man, a plan, a canal: Panama'))  # True

中心からの拡張で最長回文を求める

def longest_palindrome(s):
    best_start = best_end = 0

    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1; right += 1
        return left + 1, right - 1  # last valid bounds

    for i in range(len(s)):
        l, r = expand(i, i)      # odd-length
        if r - l > best_end - best_start:
            best_start, best_end = l, r
        l, r = expand(i, i + 1)  # even-length
        if r - l > best_end - best_start:
            best_start, best_end = l, r

    return s[best_start:best_end+1]

print(longest_palindrome('babad'))    # 'bab' or 'aba'
print(longest_palindrome('cbbd'))     # 'bb'

Manacher法の概要

# Manacher's: O(n) longest palindromic substring
def manacher(s):
    # Transform s into '#a#b#a#' to handle even/odd uniformly
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    P = [0] * n  # P[i] = palindrome radius at i
    center = right = 0
    for i in range(n):
        mirror = 2 * center - i
        if i < right:
            P[i] = min(right - i, P[mirror])
        while (i + P[i] + 1 < n and i - P[i] - 1 >= 0
               and t[i+P[i]+1] == t[i-P[i]-1]):
            P[i] += 1
        if i + P[i] > right:
            center, right = i, i + P[i]
    max_len = max(P)
    center_idx = P.index(max_len)
    start = (center_idx - max_len) // 2
    return s[start:start+max_len]

print(manacher('babad'))   # 'bab'

ランレングス符号化

def encode_rle(s):
    if not s: return ''
    parts = []
    i = 0
    while i < len(s):
        char = s[i]
        j = i
        while j < len(s) and s[j] == char:
            j += 1
        count = j - i
        parts.append(char + (str(count) if count > 1 else ''))
        i = j
    encoded = ''.join(parts)
    return encoded if len(encoded) < len(s) else s

print(encode_rle('aaabbc'))    # 'a3b2c'
print(encode_rle('abc'))       # 'abc'  (no compression gain)

ランレングス符号化文字列のデコード

def decode_rle(s):
    result = []
    i = 0
    while i < len(s):
        char = s[i]; i += 1
        num_str = ''
        while i < len(s) and s[i].isdigit():
            num_str += s[i]; i += 1
        count = int(num_str) if num_str else 1
        result.append(char * count)
    return ''.join(result)

print(decode_rle('a3b2c'))    # 'aaabbc'
print(decode_rle('a2b3c1'))   # 'aabbbc'

# Nested bracket decode (LeetCode 394)
def decode_bracket(s):
    stack = []
    for c in s:
        if c != ']':
            stack.append(c)
        else:
            chars = []
            while stack[-1] != '[':
                chars.append(stack.pop())
            stack.pop()  # remove '['
            k = int(stack.pop())
            stack.append(''.join(reversed(chars)) * k)
    return ''.join(stack)
print(decode_bracket('3[ab]'))  # 'ababab'

有効な回文 II：1文字削除可

def valid_palindrome(s):
    def is_pal(l, r):
        while l < r:
            if s[l] != s[r]: return False
            l += 1; r -= 1
        return True

    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            # Try skipping either character
            return is_pal(left+1, right) or is_pal(left, right-1)
        left += 1; right -= 1
    return True

print(valid_palindrome('aba'))    # True
print(valid_palindrome('abca'))   # True  (delete 'c')
print(valid_palindrome('abc'))    # False

回文分割 I

def partition(s):
    n = len(s)
    dp = [[False]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = True
    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] = length == 2 or dp[i+1][j-1]

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

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

最短回文：文字列ハッシュ

def shortest_palindrome(s):
    rev = s[::-1]
    combined = s + '#' + rev  # '#' prevents overlap
    n = len(combined)
    kmp = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and combined[i] != combined[j]:
            j = kmp[j-1]
        if combined[i] == combined[j]:
            j += 1
        kmp[i] = j
    # kmp[-1] = length of longest palindromic prefix
    to_add = rev[:len(s) - kmp[-1]]
    return to_add + s

print(shortest_palindrome('aacecaaa'))  # 'aaacecaaa'
print(shortest_palindrome('abcd'))      # 'dcbabcd'

確認問題

レッスンのまとめ