Programa Python para buscar strings casi similares

Dadas dos strings, la tarea aquí es escribir un programa en Python que pueda probar si son casi similares. La similitud de las strings se verifica según el criterio de diferencia de frecuencia de cada carácter, que debe ser mayor que un umbral aquí representado por K.

Entrada: test_str1 = ‘aabcdaa’, test_str2 = «abbaccd», K = 2

Salida: Verdadero

Explicación: ‘a’ aparece 4 veces en str1 y 2 veces en str2, 4 – 2 = 2, en rango, de manera similar, todos los caracteres en rango, por lo tanto, verdadero.

Entrada: test_str1 = ‘aabcdaaa’, test_str2 = «abbaccda», K = 3

Salida: Verdadero

Explicación: ‘a’ aparece 5 veces en str1 y 3 veces en str2, 5 – 3 = 2, en rango, de manera similar, todos los caracteres en rango, por lo tanto, verdadero.

Método 1: usar ascii_lowecase , comprensión de diccionario , loop y abs()

En esto, calculamos todas las frecuencias de todos los caracteres en ambas strings usando comprensión de diccionario y bucle. A continuación, cada carácter se itera a partir de los caracteres ASCII alfabéticos en minúsculas y se prueba la diferencia de frecuencia en ambas strings usando abs(), si alguna diferencia se calcula como mayor que K, el resultado se marca.

Ejemplo

from string import ascii_lowercase
 
# function to compute frequencies
 
 
def get_freq(test_str):
 
    # starting at 0 count
    freqs = {char: 0 for char in ascii_lowercase}
 
    # counting frequencies
    for char in test_str:
        freqs[char] += 1
    return freqs
 
 
# initializing strings
test_str1 = 'aabcdaa'
test_str2 = "abbaccd"
 
# printing original strings
print("The original string 1 is : " + str(test_str1))
print("The original string 2 is : " + str(test_str2))
 
# initializing K
K = 2
 
# getting frequencies
freqs_1 = get_freq(test_str1)
freqs_2 = get_freq(test_str2)
 
# checking for frequencies
res = True
for char in ascii_lowercase:
    if abs(freqs_1[char] - freqs_2[char]) > K:
        res = False
        break
 
# printing result
print("Are strings similar ? : " + str(res))

Producción:

La string original 1 es: aabcdaa

La string original 2 es: abbaccd

¿Son strings similares? : Verdadero

Método 2: Usar Counter() y max()

En esto, realizamos la tarea de obtener la frecuencia de los caracteres individuales usando Counter() y obtenemos la diferencia máxima usando max(), si es mayor que K, entonces el resultado se marca.

Ejemplo:

from collections import Counter
 
# initializing strings
test_str1 = 'aabcdaa'
test_str2 = "abbaccd"
 
# printing original strings
print("The original string 1 is : " + str(test_str1))
print("The original string 2 is : " + str(test_str2))
 
# initializing K
K = 2
 
# extracting frequencies
cnt1 = Counter(test_str1.lower())
cnt2 = Counter(test_str2.lower())
 
# getting maximum difference
res = True
if max((cnt1 - cnt2).values()) > K or max((cnt2 - cnt1).values()) > K:
    res = False
 
# printing result
print("Are strings similar ? : " + str(res))

Producción:

La string original 1 es: aabcdaa

La string original 2 es: abbaccd

¿Son strings similares? : Verdadero

La complejidad de tiempo y espacio para todos los métodos es la misma:

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(n)