Dada una array de n strings que contienen letras minúsculas. Encuentre el tamaño del subconjunto más grande de strings que son anagramas entre sí. Un anagrama de una string es otra string que contiene los mismos caracteres, solo el orden de los caracteres puede ser diferente. Por ejemplo, «abcd» y «dabc» son anagramas entre sí.
Ejemplos:
Input: ant magenta magnate tan gnamate Output: 3 Explanation Anagram strings(1) - ant, tan Anagram strings(2) - magenta, magnate, gnamate Thus, only second subset have largest size i.e., 3 Input: cars bikes arcs steer Output: 2
Tenemos una solución existente para este problema, consulte Encontrar el tamaño del subconjunto más grande del enlace de palabras de anagrama. Podemos resolver este problema rápidamente en python usando el método Counter() . El enfoque es muy simple,
- Divida la string de entrada separada por espacios en palabras.
- Como sabemos, dos strings son anagramas entre sí si contienen el mismo conjunto de caracteres. Entonces, para juntar todas esas strings primero, ordenaremos cada string en una lista dada de strings.
- Ahora cree un diccionario usando el método Counter que tenga strings como claves y sus frecuencias como valor.
- Verifique el valor máximo de frecuencias, que será el subconjunto más grande de strings de anagramas.
# Function to find the size of largest subset # of anagram words from collections import Counter def maxAnagramSize(input): # split input string separated by space input = input.split(" ") # sort each string in given list of strings for i in range(0,len(input)): input[i]=''.join(sorted(input[i])) # now create dictionary using counter method # which will have strings as key and their # frequencies as value freqDict = Counter(input) # get maximum value of frequency print (max(freqDict.values())) # Driver program if __name__ == "__main__": input = 'ant magenta magnate tan gnamate' maxAnagramSize(input)
Producción:
3
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