Sesión 64: Test Diagnóstico 1 — Programación Dinámica Bidimensional y Backtracking: Regex Matching (LeetCode 10 Hard)#

Tiempo estimado: 75-85 minutos. Nivel: De Junior/Trainee a Staff Specialist. Herramientas obligatorias: Hoja cuadriculada, lápiz, regla y bolígrafos de dos colores.

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

Consulta rápida: Glosario Maestro | Guía de Diagramas

Regular Expression Matching (Coincidencia de Expresiones Regulares)#

• (a) En palabras simples (intuición): Es un validador que comprueba si una palabra completa cumple con una plantilla o molde. A diferencia de un buscador que encuentra una subcadena en medio de un texto, aquí la palabra entera debe coincidir de principio a fin con el molde.
• (b) Definición técnica paso a paso: Problema de decisión de autómatas finitos que determina si una cadena de texto S pertenece al lenguaje formal generado por un patrón P:
• Caracteres literales (a-z): Coinciden exactamente con el mismo carácter.
• Carácter punto (.): Comodín que coincide con cualquier carácter único individual.
• Carácter asterisco (*): Modificador posfijo que representa cero o más repeticiones del carácter que lo precede inmediatamente.
• (c) Cómo funciona en Rust (memoria y tipos): En Rust, los strings &str usan codificación UTF-8 de longitud variable (donde un carácter puede ocupar de 1 a 4 bytes). Acceder a s[i] por índice directo no está permitido por el compilador para evitar tiempos lineales ocultos. Por ende, convertimos las cadenas en vectores contiguos de caracteres en el Heap Vec<char> para garantizar indexación en tiempo O(1).
• (d) Error típico de Junior: Tratar al asterisco * como un comodín independiente (estilo shell *.txt). En expresiones regulares estándar, el * nunca va solo; es un cuantificador que modifica exclusivamente al símbolo previo (por ejemplo: a* o .*).

Matriz de Programación Dinámica Bidimensional (dp[i][j])#

• (a) En palabras simples (intuición): Es una tabla cuadriculada donde las filas son los prefijos de tu texto y las columnas son los prefijos de tu patrón. La celda en la fila i, columna j guarda una respuesta booleana simple: "¿los primeros i caracteres de mi texto coinciden perfectamente con los primeros j caracteres de mi patrón?".
• (b) Definición técnica paso a paso: Estado bidimensional de tamaño (|S| + 1) × (|P| + 1):
• dp[i][j] = true si S[0..i] hace match con P[0..j], false en caso contrario.
• La fila 0 y columna 0 representan la cadena vacía ε y el patrón vacío ε.
• (c) Cómo funciona en Rust (memoria y tipos): Se asigna un vector bidimensional vec![vec![false; n + 1]; m + 1] en el Heap. La memoria total consumida es de (M + 1) × (N + 1) bytes booleanos contiguos.
• (d) Error típico de Junior: Dimensionar la matriz como M × N en lugar de (M + 1) × (N + 1), perdiendo la representación del caso base de cadena vacía e introduciendo errores de off-by-one.

Transición del Operador Asterisco (p[j-1] == '*')#

• (a) En palabras simples (intuición): Cuando ves una letra seguida de asterisco (como a*), tienes dos caminos posibles:

1. El camino de ignorar (0 veces): Pretendes que a* no existe y miras si tu texto ya coincidía con el patrón que estaba antes de la a (retrocedes 2 columnas en la tabla).
2. El camino de consumir (1 o más veces): Si el último carácter de tu texto es una a (o un .), consumes esa a de tu texto y te preguntas: "¿el resto de mi texto coincidía con este mismo patrón a*?" (subes 1 fila en la tabla manteniendo la misma columna).

• (b) Definición técnica paso a paso: La bifurcación lógica se formula como:

• (c) Cómo funciona en Rust (memoria y tipos): La evaluación perezosa del operador || en Rust garantiza que si la opción de 0 repeticiones es true, la segunda expresión no se evalúa, ahorrando lecturas a la matriz.
• (d) Error típico de Junior: Intentar hacer un bucle while que cuente cuántas repeticiones de la letra hay en S; esto dispara la complejidad temporal a O(N³) en vez de O(M · N).

Backtracking con Memoización Top-Down#

• (a) En palabras simples (intuición): Es como explorar un laberinto con un cuaderno de notas. En cada bifurcación de *, pruebas primero el camino de saltar el asterisco. Si llegas a un callejón sin salida, regresas y pruebas el camino de consumir letras. Para no explorar el mismo punto dos veces, anotas en tu libreta: "en la posición (i=3, j=5) la respuesta fue falso".
• (b) Definición técnica paso a paso: Algoritmo recursivo de búsqueda en profundidad (DFS) sobre el árbol de estados (i, j) que utiliza una tabla Hash HashMap<(usize, usize), bool> para cachear resultados previamente computados.
• (c) Cómo funciona en Rust (memoria y tipos): La tabla hash memo reside en el Heap y se pasa por referencia mutable &mut en cada marco del Call Stack, evitando clones.
• (d) Error típico de Junior: Omitir la memoización en la solución recursiva, lo que provoca una explosión combinatoria exponencial O(2^{M+N}) que bloquea la ejecución.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Tabla de Transiciones de Estado para LeetCode 10#

Analicemos cómo se llena la matriz celda por celda para S = "aab" y P = "c*a*b":

1. Inicialización de la fila 0 (Cadena Vacía S = ε): - dp[0][0] = true (ε coincide con ε). - Para P[1] = 'c', dp[0][1] = false. - Para P[2] = '*', miramos dos posiciones atrás: dp[0][2] = dp[0][0] = true (porque c* puede ser 0 veces c). - Para P[3] = 'a', dp[0][3] = false. - Para P[4] = '*', miramos dos posiciones atrás: dp[0][4] = dp[0][2] = true (porque a* puede ser 0 veces a). - Para P[5] = 'b', dp[0][5] = false.

Fila 0 completa: [T, F, T, F, T, F]

1. Llenado de filas subsiguientes: - Al evaluar S[2] = 'a' y P[4] = '*', tenemos: - Opción 1: dp[2][2] (0 veces a) → ¿"aa" coincide con "c"? Es false. - Opción 2: S[1] == 'a' y dp[1][4] (1 o más veces a) → ¿"a" coincide con "ca*"? Es true. - Resultado: false lor true = true. - Al llegar a la última celda dp[3][5], el resultado final es true.

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama Arquitectónico de Flujo#

Consulta el diagrama vectorial:

flowchart TD
    PAT{"¿p[j-1] == '*'?"}
    PAT -->|Sí| ZERO["Opción 1 (0 repeticiones):<br/>dp[i][j-2]"]
    PAT -->|Sí| MORE["Opción 2 (1+ repeticiones):<br/>s[i-1] matches p[j-2] && dp[i-1][j]"]
    ZERO & MORE --> COMB["dp[i][j] = zero || more"]
    PAT -->|No| NORM["s[i-1] matches p[j-1] ?<br/>dp[i-1][j-1] : false"]

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Matriz dp para S = "aab" y P = "c*a*b":

Dimensiones: (|S| + 1) = 4 filas, (|P| + 1) = 6 columnas.

Stack:
  m = 3, n = 5
  dp: [ptr, cap: 4, len: 4]

Heap (Matriz de Booleanos dp[i][j]):
        ε     c     *     a     *     b
      j=0   j=1   j=2   j=3   j=4   j=5
ε i=0 [ T ,   F ,   T ,   F ,   T ,   F ]
a i=1 [ F ,   F ,   F ,   T ,   T ,   F ]
a i=2 [ F ,   F ,   F ,   F ,   T ,   F ]
b i=3 [ F ,   F ,   F ,   F ,   F ,   T ] <-- dp[3][5] = TRUE (MATCH EXITOSO)

TRAZA DEL RESULTADO FINAL EN dp[3][5]:
- Carácter actual de S: 'b' (índice i=3)
- Carácter actual de P: 'b' (índice j=5)
- Como 'b' == 'b', hereda dp[i-1][j-1] = dp[2][4].
- ¿Qué había en dp[2][4]? Había 'T' (la subcadena "aa" coincide con "c*a*").
- Por lo tanto, dp[3][5] = true.

4. Implementación Canónica en Rust (Compilable con rustc --test)#

Archivo de referencia: practica-rust/dia_64.rs

use std::collections::HashMap;

/// LeetCode 10: Regular Expression Matching con DP 2D Bottom-Up en O(|s| * |p|)
pub fn is_match_dp(s: &str, p: &str) -> bool {
    let s_chars: Vec<char> = s.chars().collect();
    let p_chars: Vec<char> = p.chars().collect();
    let m = s_chars.len();
    let n = p_chars.len();

    let mut dp = vec![vec![false; n + 1]; m + 1];
    dp[0][0] = true;

    for j in 1..=n {
        if p_chars[j - 1] == '*' && j >= 2 {
            dp[0][j] = dp[0][j - 2];
        }
    }

    for i in 1..=m {
        for j in 1..=n {
            if p_chars[j - 1] == '*' {
                if j < 2 {
                    continue;
                }
                let zero_match = dp[i][j - 2];
                let char_matches = p_chars[j - 2] == '.' || p_chars[j - 2] == s_chars[i - 1];
                let more_match = char_matches && dp[i - 1][j];
                dp[i][j] = zero_match || more_match;
            } else {
                let char_matches = p_chars[j - 1] == '.' || p_chars[j - 1] == s_chars[i - 1];
                if char_matches {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
    }

    dp[m][n]
}

/// Implementación alternativa mediante Backtracking con Memoización Top-Down
pub fn is_match_backtracking(s: &str, p: &str) -> bool {
    let s_chars: Vec<char> = s.chars().collect();
    let p_chars: Vec<char> = p.chars().collect();
    let mut memo: HashMap<(usize, usize), bool> = HashMap::new();

    fn dfs(s: &[char], p: &[char], i: usize, j: usize, memo: &mut HashMap<(usize, usize), bool>) -> bool {
        if let Some(&cached) = memo.get(&(i, j)) {
            return cached;
        }
        if j == p.len() {
            return i == s.len();
        }

        let first_match = i < s.len() && (p[j] == '.' || p[j] == s[i]);

        let result = if j + 1 < p.len() && p[j + 1] == '*' {
            dfs(s, p, i, j + 2, memo) || (first_match && dfs(s, p, i + 1, j, memo))
        } else {
            first_match && dfs(s, p, i + 1, j + 1, memo)
        };

        memo.insert((i, j), result);
        result
    }

    dfs(&s_chars, &p_chars, 0, 0, &mut memo)
}

Implementación de Referencia en Python Tipado#

from typing import Dict, Tuple


def is_match_dp_py(s: str, p: str) -> bool:
    """LeetCode 10 con DP 2D Bottom-Up en O(M * N)."""
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    for j in range(1, n + 1):
        if p[j - 1] == "*" and j >= 2:
            dp[0][j] = dp[0][j - 2]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                zero = dp[i][j - 2]
                match_char = p[j - 2] in (s[i - 1], ".")
                more = match_char and dp[i - 1][j]
                dp[i][j] = zero or more
            else:
                match_char = p[j - 1] in (s[i - 1], ".")
                if match_char:
                    dp[i][j] = dp[i - 1][j - 1]

    return dp[m][n]

5. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

6. Navegación#

• ← Sesión 63: CTCI Cap. 6 — Super Egg Drop y Consolidación
• Sesión 65: Test Diagnóstico 2 — Tries Compuestos y DSU Avanzado →
• Mapa del Curso
• Glosario Maestro
• Guía de Diagramas de Arquitectura