Dadas dos strings str y pattern , encuentre la substring más pequeña en str que contenga todos los caracteres del patrón de manera eficiente.
Ejemplos:
Input : str = 'geeksforgeeks' pattern = 'gks' Output : geeks Input : str = 'new string' pattern = 'rg' Output : ring
Enfoque #1: Usar Python enumerate()
Este método usa Python enumerate(). need[k] almacena cuántas veces necesitamos el carácter k y falta indica cuántos caracteres aún faltan. En el ciclo, primero agregue el nuevo carácter a la ventana. Luego, si no falta nada, elimine todo lo que pueda de la ventana de inicio y luego actualice el resultado.
string = 'new string' pattern = 'rg' # let's find the index of r and g in String and the # stor them in index list (index[]) index=[] for x in range(len(pattern)): if pattern[x] in string: index.append(string.index(pattern[x])) # sorting the r and g index's index.sort() # save first index in l l = len(index) low = int(index[0]) # save last index in h high = int(index[l-1]) h = high +1 for i in range(low,h): print(string[i],end=" ")
ksf
Enfoque n. ° 2: al usar collections.defaultdict()
este método, haga uso de dos dictados predeterminados ‘src’ y ‘dest’. Un dictado predeterminado funciona exactamente como un dictado normal, pero se inicializa con una función («fábrica predeterminada») que no acepta argumentos. el origen está vacío, mientras que el destino consta de elementos de patrón como claves y el recuento de ocurrencias como valor. En cada iteración ‘i’, verificamos si el i -ésimo elemento de str está presente en el diccionario de destino o no y actualizamos el diccionario de origen en consecuencia.
# Python3 code to Find the smallest # window in a string containing all # characters of another string from collections import defaultdict import sys def min_window(str, pattern): # Function to check validity of source and # destination def isValid(i, j): for item in j: if item not in i or i[item] < j[item]: return False return True source = defaultdict(int) target = defaultdict(int) # Target consist pattern elements and 1 # as key:value pair for e in pattern: target[e] += 1 # Minimum length for window minLen = sys.maxsize n = len(str) ans, j = '', 0 for i in range(n): # Update source for valid source - target pair while j < n and (isValid(source, target) == False): source[str[j]] += 1 j += 1 # Checking validity of source-target pair if isValid(source, target): if minLen > j-i + 1: minLen = j-i + 1 ans = str[i:j] source[str[i]] -= 1 return ans # Driver Code string = "geekforgeeks" pattern = "gks" print(min_window(string, pattern))
geeks
Enfoque #3: Enfoque dinámico
En este método, usamos un ciclo for y en cada iteración, digamos i, encontramos el intervalo más corto que termina en i e incluye todas las letras en el patrón. Esto se puede hacer teniendo en cuenta dos estructuras de datos, es decir, ‘rpos’ y ‘rdict’. rpos es una lista ordenada de posiciones donde se mantienen las posiciones más a la derecha de los caracteres del patrón en str y rdict es una asignación de diccionario de un carácter a la posición. Los valores de rdict son los mismos que rpos.
# Python3 code to Find the smallest # window in a string containing all # characters of another string from collections import Counter, defaultdict def min_window(str, pattern): rdict, count = defaultdict(list), Counter(pattern) rpos, res = [], "" # Loop only over c exist in pattern for i, c in filter(lambda x: x[1] in pattern, enumerate(str)): if len(rdict) == count: # If reached limit, remove rpos.remove(rdict.pop(0)) # Add to dict rdict[i].append(i) # Add to list rpos.append(i) if (len(rpos) == len(pattern) and (res =="" or rpos[-1]-rpos[0]<len(res))): res = str[rpos[0]:rpos[-1]+1] return res # Driver Code string = "geeksforgeeks" pattern = "gks" print(min_window(string, pattern))
geeks
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