Sətirlərin emalı və sıxılması

Bu mövzuda sətirləri əllə təhlil edirik: sıxırıq, ifadə hesablayırıq, mötərizələri yoxlayırıq və sətir yığmağın qiymətini öyrənirik. Hamısı eyni sxemlə həll olunur: sətri bir dəfə keçib kiçik vəziyyət saxlayırıq, ona görə vaxt O(n)-dir. Əvvəlki mövzu: palindromlar və anaqramlar.

Seriya uzunluğu ilə kodlaşdırma (RLE)

Seriya eyni simvolların ardıcıl blokudur. RLE hər seriyanı simvol + say ilə əvəz edir. Alqoritm: s[i]-ni s[i - 1] ilə müqayisə edib sayı artırırıq, seriya bitəndə nəticəyə yazırıq. Sonuncu seriya dövrdən sonra yazılır. Vaxt O(n), yaddaş O(n). Üstünlük uzun seriyalarda ("a" * 100 → a100), çatışmazlıq tək simvollarda (abc → a1b1c1, iki dəfə uzun).

def rle_encode(s):
    if not s:
        return ""
    out = []
    count = 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            count += 1
        else:
            out.append(s[i - 1] + str(count))
            count = 1
    out.append(s[-1] + str(count))
    return "".join(out)

import re

def rle_decode(t):
    return "".join(ch * int(n) for ch, n in re.findall(r"(\D)(\d+)", t))