py_palindrome_partitioner · Python
▶ Aprender py_palindrome_partitioner (Python) paso a paso · explicación de py_palindrome_partitioner
Código línea a línea
Tres columnas: el código, el trozo del subject o del main que obliga a escribir esa línea, y el por qué.
py_palindrome_partitioner.py
| Código | Subject | Por qué |
|---|---|---|
def palindrome_partitioner(s: str) -> int: | def palindrome_partitioner(s: str) -> int: | Firma del subject. |
n = len(s) | Longitud. | |
cuts = list(range(-1, n)) | In the worst case (all characters are distinct), the result is len(s) - 1 cuts. | cuts[i] = mínimo de cortes para el prefijo de longitud i. Arranco con el peor caso, i - 1. cuts[0] = -1 es el truco: "un corte antes del principio" que se anula al sumar 1. |
for center in range(n): | every resulting substring is a palindrome | Para encontrar todos los palíndromos, expando desde cada centro. |
for lo, hi in ((center, center), (center, center + 1)): | Dos centros por posición: el carácter (palíndromos de longitud impar) y el hueco entre él y el siguiente (longitud par). | |
while lo >= 0 and hi < n and s[lo] == s[hi]: | Mientras los extremos coincidan, s[lo..hi] es palíndromo. | |
cuts[hi + 1] = min(cuts[hi + 1], cuts[lo] + 1) | find the minimum number of cuts needed to partition it | Si s[lo..hi] es palíndromo, el prefijo hasta hi se puede hacer con los cortes del prefijo hasta lo más un corte. Me quedo con el mínimo. |
lo -= 1 | Expando. | |
hi += 1 | Hacia los dos lados. | |
return max(cuts[n], 0) | An empty string or a string of length 1 is already a palindrome -> 0 cuts. | La respuesta es el prefijo completo. El max es por el string vacío: cuts[0] es -1. |