Dada una string y un entero k, escriba un programa de Python para encontrar todas las substrings posibles de la string dada después de eliminar k caracteres.
Ejemplos:
Input : geeks, k = 1
Output : {'gees', 'eeks', 'geks', 'geek'}
Input : dog, k = 1
Output : {'do', 'dg', 'og'}
Enfoque n.° 1: enfoque ingenuo
Este es el enfoque ingenuo recursivo para encontrar todas las substrings posibles después de eliminar k caracteres. Primero, inicializamos la variable de inicio, fin e índice con 0, longitud de string y 0 respectivamente. Creamos una lista temporal, digamos ‘ temp ‘ que almacena todas las salidas una por una. Comenzamos desde el primer índice en temp[], uno por uno fijamos elementos en este índice y recurrimos para los índices restantes.
# Python3 program to Find all combinations # of string after deleting k characters list = [] def findCombinations(str, temp, start, end, index, k): if (index == k): item = '' for j in range(k): item += temp[j] list.append(item) return; i = start; while(i <= end and end - i + 1 >= k - index): temp[index] = str[i] findCombinations(str, temp, i + 1, end, index + 1, k); i += 1; # Driver Code str = 'geeks' k = 1 temp = [0]*(len(str)-k) s, e = 0, len(str)-1 findCombinations(str, temp, s, e, 0, len(str)-k) print(set(list))
{'eeks', 'gees', 'geks', 'geek'}
Enfoque #2: Uso de Itertools
El módulo Itertools de Python proporciona una función combination(), que toma la string y la longitud para dar todas las combinaciones posibles de una string.
# Python3 program to Find all combinations # of string after deleting k characters from itertools import combinations def findCombinations(str, k): l = len(str) return set([''.join(i) for i in combinations(str, l - k)]) # Driver Code str = 'geeks' k = 1 print(findCombinations(str, k))
{'geek', 'eeks', 'geks', 'gees'}
Publicación traducida automáticamente
Artículo escrito por Smitha Dinesh Semwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA