Dadas dos strings, encuentre si podemos hacer la primera string a partir de la segunda eliminando algunos caracteres de la segunda y reorganizando los caracteres restantes.
Ejemplos:
Input : s1 = ABHISHEKsinGH
: s2 = gfhfBHkooIHnfndSHEKsiAnG
Output : Possible
Input : s1 = Hello
: s2 = dnaKfhelddf
Output : Not Possible
Input : s1 = GeeksforGeeks
: s2 = rteksfoGrdsskGeggehes
Output : Possible
Tenemos una solución existente para este problema, consulte Crear una string a partir de otra mediante la eliminación y reorganización del enlace de caracteres. Trataremos este problema rápidamente en python. El enfoque es muy simple,
- Convierta ambas strings en un diccionario usando el método Counter (iterable) , cada diccionario contiene caracteres dentro de la string como Clave y sus frecuencias como Valor.
- Ahora tome la intersección de dos diccionarios y compare la salida resultante con el diccionario de la primera string, si ambos son iguales, eso significa que es posible convertir la string, de lo contrario no.
Implementación:
Python3
# Python code to find if we can make first string
# from second by deleting some characters from
# second and rearranging remaining characters.
from collections import Counter
def makeString(str1,str2):
# convert both strings into dictionaries
# output will be like str1="aabbcc",
# dict1={'a':2,'b':2,'c':2}
# str2 = 'abbbcc', dict2={'a':1,'b':3,'c':2}
dict1 = Counter(str1)
dict2 = Counter(str2)
# take intersection of two dictionaries
# output will be result = {'a':1,'b':2,'c':2}
result = dict1 & dict2
# compare resultant dictionary with first
# dictionary comparison first compares keys
# and then compares their corresponding values
return result == dict1
# Driver program
if __name__ == "__main__":
str1 = 'ABHISHEKsinGH'
str2 = 'gfhfBHkooIHnfndSHEKsiAnG'
if (makeString(str1,str2)==True):
print("Possible")
else:
print("Not Possible")
Producción
Possible
Publicación traducida automáticamente
Artículo escrito por Shashank Mishra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA