Estoy tomando un curso de Udemy. El problema en el que estoy trabajando es tomar dos cadenas y determinar si están 'a una edición de distancia' una de la otra. Eso significa que puede hacer un solo cambio: cambiar una letra, agregar una letra, eliminar una letra, de una cadena y hacer que se vuelva idéntica a la otra.

Ejemplos:

s1a = "abcde"
s1b = "abfde"

s2a = "abcde"
s2b = "abde"

s3a = "xyz"
s3b = "xyaz"
  • s1a cambia el 'c' a un 'f'.
  • s2a elimina 'c'.
  • s3a agrega 'a'.

La solución de instructores (y suite de pruebas):

def is_one_away(s1, s2):
    if len(s1) - len(s2) >= 2 or len(s2) - len(s1) >= 2:
        return False
    elif len(s1) == len(s2):
        return is_one_away_same_length(s1, s2)
    elif len(s1) > len(s2):
        return is_one_away_diff_lengths(s1, s2)
    else:
        return is_one_away_diff_lengths(s2, s1)


def is_one_away_same_length(s1, s2):
    count_diff = 0
    for i in range(len(s1)):
        if not s1[i] == s2[i]:
            count_diff += 1
            if count_diff > 1:
                return False
    return True


# Assumption: len(s1) == len(s2) + 1
def is_one_away_diff_lengths(s1, s2):
    i = 0
    count_diff = 0
    while i < len(s2):
        if s1[i + count_diff] == s2[i]:
            i += 1
        else:
            count_diff += 1
            if count_diff > 1:
                return False
    return True


# NOTE: The following input values will be used for testing your solution.
print(is_one_away("abcde", "abcd"))  # should return True
print(is_one_away("abde", "abcde"))  # should return True
print(is_one_away("a", "a"))  # should return True
print(is_one_away("abcdef", "abqdef"))  # should return True
print(is_one_away("abcdef", "abccef"))  # should return True
print(is_one_away("abcdef", "abcde"))  # should return True
print(is_one_away("aaa", "abc"))  # should return False
print(is_one_away("abcde", "abc"))  # should return False
print(is_one_away("abc", "abcde"))  # should return False
print(is_one_away("abc", "bcc"))  # should return False

Cuando vi el problema, decidí abordarlo usando set().

Encontré esto muy informativo: ¿Opuesto a set.intersection en Python?

Este es mi intento de solución:

def is_one_away(s1, s2):
    if len(set(s1).symmetric_difference(s2)) <= 1:
        return True

    if len(set(s1).symmetric_difference(s2)) == 2:
        if len(set(s1).difference(s2)) == len(set(s2).difference(s1)):
            return True
        return False
    return False

Cuando ejecuto mi solución en línea (puede probar dentro del curso en sí), estoy fallando en el último elemento del conjunto de pruebas:

False != True : 
Input 1: abc
Input 2: bcc
Expected Result: False
Actual Result: True

Lo intenté y lo intenté, pero no puedo hacer que funcione el último elemento de prueba (al menos no sin romper un montón de otras cosas).

No hay garantía de que pueda resolver el conjunto de pruebas completo con una solución basada en set(), pero como estoy a un artículo de distancia, realmente quería ver si podía hacerlo.

1
MarkS 23 ene. 2018 a las 15:53

3 respuestas

La mejor respuesta

Esto no pasa esta prueba, porque solo mira caracteres únicos :

>>> s1 = 'abc'
>>> s2 = 'bcc'
>>> set(s1).symmetric_difference(s2)
{'a'}

Es un conjunto de longitud 1, pero hay dos caracteres cambiados. Al convertir a un conjunto, solo ve que hay al menos un carácter 'c' en la entrada s2, no que ahora haya dos.

Otra forma en que su enfoque fallaría sería si el orden de los caracteres cambiara. 'abc' está a dos cambios de 'cba', pero su enfoque no podrá detectar esos cambios también.

No puede resolver este problema utilizando conjuntos, porque los conjuntos eliminan dos datos importantes: cuántas veces aparece un carácter y en qué orden se enumeran los caracteres.

6
cs95 23 ene. 2018 a las 14:43

Aquí está resolviendo uno donde se usa set para encontrar el personaje único. Hecho no completamente usando set, pero set se usa para encontrar el carácter único en dos cadenas dadas. La lista como una pila se utiliza para extraer elementos de ambas pilas y luego compararlos.

Usando la pila, saque elementos de ambos elementos y vea si coinciden. Encuentre el elemento de carácter único, y cuando el elemento emergente coincida con un carácter único, debemos volver a mostrar la primera cadena.

Por ejemplo, palidece y palidece cuando se encuentra s, deberíamos hacer estallar nuevamente. pale pale sería cierto porque s es un carácter único y cuando se abre s, volveremos a mostrar string1. Si los caracteres emergentes no coinciden mayores que 1, podemos devolver False.

def one_away(string1: str, string2: str) -> bool:
    string1, string2 = [ char for char in string1.replace(" ","").lower() ], [ char for char in string2.replace(" ","").lower() ]
    if len(string2) > len(string1):
        string1, string2 = string2, string1
    len_s1, len_s2, unmatch_count = len(string1), len(string2), 0

    if len_s1 == len_s2 or len_s1 - len_s2 == 1:
        unique_char = list(set(string1) - set(string2)) or ["None"]
        if unique_char[0] == "None" and len_s1 - len_s2 == 1:
            return True # this is for "abcc" "abc"
        while len(string1) > 0:
            pop_1, pop_2 = string1.pop(), string2.pop()
            if pop_1 == unique_char[0] and len_s1 - len_s2 == 1: 
                pop_1 = string1.pop()
            if pop_1 != pop_2:
                unmatch_count += 1
            if unmatch_count > 1:
                return False
        return True
    return False

Por ejemplo prueba:

strings = [("abc","ab"), ("pale", "bale"), ("ples", "pale"), ("palee", "pale"), ("pales", "pale"), ("pale", "ple"), ("abc", "cab"), ("pale", "bake")]
for string in strings:
    print(f"{string} one_away: {one_away(string[0]), string[1]}")
('pale', 'bale') one_away: True
('ples', 'pale') one_away: False
('palee', 'pale') one_away: True
('pales', 'pale') one_away: True
('pale', 'ple') one_away: True
('abc', 'cab') one_away: False
('pale', 'bake') one_away: False
0
Rakib Fiha 26 dic. 2020 a las 07:43

Aquí hay una solución que utiliza las diferencias encontradas por comprensión de listas.

def one_away(s1, s2):
    diff1 = [el for el in s1 if el not in s2]
    diff2 = [el for el in s2 if el not in s1]
    if len(diff1) < 2 and len(diff2) < 2:
        return True
    return False

A diferencia de una solución basada en conjuntos, esta no pierde información vital sobre personajes no únicos.

1
mxkzk 9 abr. 2020 a las 20:27