🐍 Python: Solución al problema '383. Ransom Note' en Python

💡 Este es un problema interesante que nos ayuda a mejorar nuestra lógica en Python.

🎯 Objetivo: Verificar si podemos construir una ransomNote usando las letras de magazine, sin repetir ninguna más veces de lo que aparece en magazine.

🔹 Ejemplo 1:

Input: ransomNote = "a", magazine = "b"
Output: False

🔹 Ejemplo 2:

Input: ransomNote = "aa", magazine = "ab"
Output: False

🔹 Ejemplo 3:

Input: ransomNote = "aa", magazine = "aab"
Output: True

🚀 Mi solución en Python

Para resolver el problema, seguimos un enfoque directo: recorremos cada letra de ransomNote y verificamos si está en magazine. Si está, la eliminamos (para evitar repetirla). Si no, retornamos False.

def canConstruct(ransomNote: str, magazine: str) -> bool:
    for letraR in ransomNote:
        if letraR in magazine:
            magazine = magazine.replace(letraR, "", 1)
        else:
            return False
    return True

🔍 Explicación paso a paso

1️⃣ Recorremos cada letra letraR en ransomNote.
2️⃣ Comprobamos si está en magazine.

• ✅ Si está, la eliminamos con replace(letraR, "", 1).
• ❌ Si no está, retornamos False.

3️⃣ Si logramos recorrer todo ransomNote, retornamos True porque logramos formar la palabra.

⏳ Complejidad

🔹 Como iteramos sobre ransomNote y usamos replace(), la complejidad en el peor caso es O(n × m).
🔹 replace() recorre todo magazine en cada iteración, lo que puede ser ineficiente para cadenas largas.

⚡ Optimización con Counter

Para mejorar la eficiencia, podemos usar collections.Counter para contar las ocurrencias de cada letra en ransomNote y magazine:

from collections import Counter

def canConstruct(ransomNote: str, magazine: str) -> bool:
    countRansom = Counter(ransomNote)
    countMagazine = Counter(magazine)

    for letra, cantidad in countRansom.items():
        if countMagazine[letra] < cantidad:
            return False
    return True

🎯 Ventajas de esta versión:

✅ Más eficiente: Su complejidad es O(n + m), ya que construimos los contadores en O(n) y O(m) y luego los recorremos en O(n).
✅ Código más claro y fácil de leer.