Como encontrar a menor substring que contém todos os caracteres de uma determinada string?

Recentemente, me deparei com uma pergunta interessante sobre strings. Suponha que você receba o seguinte:

Input string1: "this is a test string" Input string2: "tist" Output string: "t stri" 

Então, dado acima, como posso me aproximar para encontrar a menor substring da string1 que contém todos os caracteres da string 2?

Você pode fazer uma varredura de histograma em tempo O(N+M) e O(1) espaço em que N é o número de caracteres na primeira cadeia e M é o número de caracteres na segunda.

Funciona assim:

  • Faça um histograma dos caracteres da segunda string (a operação da tecla é hist2[ s2[i] ]++ ).
  • Faça um histograma cumulativo dos caracteres da primeira string até que o histograma contenha todos os caracteres que o histograma da segunda string contenha (o que chamarei de “condição do histograma”).
  • Em seguida, avance na primeira string, subtraindo do histograma, até que ela não atenda à condição do histograma. Marque esse bit da primeira string (antes do movimento final) como sua substring tentativa.
  • Mova a frente da substring para a frente novamente até encontrar a condição do histograma novamente. Mova a extremidade para frente até que ela falhe novamente. Se esta for uma substring mais curta que a primeira, marque isso como sua substring tentativa.
  • Repita até que você tenha passado pela primeira string inteira.
  • A substring marcada é sua resposta.

Observe que, ao variar a verificação usada na condição do histograma, você pode optar por ter o mesmo conjunto de caracteres que a segunda sequência ou pelo menos tantos caracteres de cada tipo . (É apenas a diferença entre a[i]>0 && b[i]>0 e a[i]>=b[i] .)

Você pode acelerar as verificações de histograma se você mantiver uma faixa de qual condição não está satisfeita quando você está tentando satisfazê-la, e verificar apenas a coisa que você decrementa quando você está tentando quebrá-la. (No acúmulo inicial, você conta quantos itens você tem satisfeito e incrementa essa contagem toda vez que você adiciona um novo caractere que leva a condição de falso para verdadeiro.)

Para ver mais detalhes, incluindo o código de trabalho, confira a postagem do meu blog em:

http://www.leetcode.com/2010/11/finding-minimum-window-in-s-which.html

Para ajudar a ilustrar essa abordagem, uso um exemplo: string1 = "acbbaca" e string2 = "aba" . Aqui, também usamos o termo “janela”, que significa um bloco contíguo de caracteres da string1 (pode ser intercambiado com o termo substring).

texto alternativo

i) string1 = “acbbaca” e string2 = “aba”.

texto alternativo

ii) A primeira janela mínima é encontrada. Observe que não podemos avançar o ponteiro como hasFound [‘a’] == needToFind [‘a’] == 2. Avançar significaria quebrar a restrição.

texto alternativo

iii) A segunda janela é encontrada. begin pointer ainda aponta para o primeiro elemento ‘a’. hasFound [‘a’] (3) é maior que needToFind [‘a’] (2). Diminuímos hasFound [‘a’] em um e avançamos o ponteiro para a direita.

texto alternativo

iv) Ignoramos ‘c’, uma vez que não é encontrado em string2. Iniciar ponteiro agora aponta para ‘b’. hasFound [‘b’] (2) é maior que needToFind [‘b’] (1). Diminuímos hasFound [‘b’] em um e avançamos o ponteiro para a direita.

texto alternativo

v) O ponteiro inicial agora aponta para o próximo ‘b’. hasFound [‘b’] (1) é igual a needToFind [‘b’] (1). Paramos imediatamente e esta é a nossa janela mínima recentemente encontrada.

A idéia é baseada principalmente na ajuda de dois pointers (posição inicial e final da janela) e duas tabelas (needToFind e hasFound) ao atravessar string1. needToFind armazena a contagem total de um caractere em string2 e hasFound armazena a contagem total de um caractere encontrado até o momento. Também usamos uma variável count para armazenar o total de caracteres em string2 que foi atendido até o momento (sem contar os caracteres em que hasFound [x] excede needToFind [x]). Quando count é igual a string2, sabemos que uma janela válida é encontrada.

Cada vez que avançamos o ponteiro final (apontando para um elemento x), incrementamos hasFound [x] em um. Nós também incrementamos a contagem por um se hasFound [x] for menor ou igual a needToFind [x]. Por quê? Quando a restrição é atendida (ou seja, a contagem é igual ao tamanho da string2), avançamos imediatamente para iniciar o ponteiro o mais longe possível, mantendo a restrição.

Como podemos verificar se está mantendo a restrição? Suponha que comece apontando para um elemento x, nós verificamos se hasFound [x] é maior que needToFind [x]. Se for, podemos decrementar hasFound [x] em um e avançar o ponteiro sem quebrar a restrição. Por outro lado, se não for, paramos imediatamente quando o ponteiro begin começa a quebrar a restrição da janela.

Finalmente, verificamos se o tamanho mínimo da janela é menor que o mínimo atual. Atualize o mínimo atual se um novo mínimo for encontrado.

Essencialmente, o algoritmo encontra a primeira janela que satisfaz a restrição e, em seguida, continua mantendo a restrição por toda parte.

Aqui está uma solução O (n). A idéia básica é simples: para cada índice inicial, localize o índice de menor final, de forma que a substring contenha todas as letras necessárias. O truque é que o índice de menor finalização aumenta ao longo da function, portanto, com um pouco de suporte à estrutura de dados, consideramos cada caractere no máximo duas vezes.

Em Python:

 from collections import defaultdict def smallest(s1, s2): assert s2 != '' d = defaultdict(int) nneg = [0] # number of negative entries in d def incr(c): d[c] += 1 if d[c] == 0: nneg[0] -= 1 def decr(c): if d[c] == 0: nneg[0] += 1 d[c] -= 1 for c in s2: decr(c) minlen = len(s1) + 1 j = 0 for i in xrange(len(s1)): while nneg[0] > 0: if j >= len(s1): return minlen incr(s1[j]) j += 1 minlen = min(minlen, j - i) decr(s1[i]) return minlen 

Eu recebi a mesma pergunta da entrevista. Eu sou um candidato C ++, mas eu estava em posição de codificar relativamente rápido em JAVA.

Java [Cortesia: Sumod Mathilakath]

 import java.io.*; import java.util.*; class UserMainCode { public String GetSubString(String input1,String input2){ // Write code here... return find(input1, input2); } private static boolean containsPatternChar(int[] sCount, int[] pCount) { for(int i=0;i<256;i++) { if(pCount[i]>sCount[i]) return false; } return true; } public static String find(String s, String p) { if (p.length() > s.length()) return null; int[] pCount = new int[256]; int[] sCount = new int[256]; // Time: O(p.lenght) for(int i=0;i 

C ++ [Cortesia: sundeepblue]

 #include  #include  #include  #include  using namespace std; string find_minimum_window(string s, string t) { if(s.empty() || t.empty()) return; int ns = s.size(), nt = t.size(); vector total(256, 0); vector sofar(256, 0); for(int i=0; i total[c]) { sofar[c]--; L++; } else break; } if(R - L + 1 < min_win_len) { // this judge should be inside POS1 min_win_len = R - L + 1; minL = L; } } } string res; if(count == nt) // gist3, cannot forget this. res = s.substr(minL, min_win_len); // gist4, start from "minL" not "L" return res; } int main() { string s = "abdccdedca"; cout << find_minimum_window(s, "acd"); } 

Erlang [Cortesia: wardbekker]

 -module(leetcode). -export([min_window/0]). %% Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). %% For example, %% S = "ADOBECODEBANC" %% T = "ABC" %% Minimum window is "BANC". %% Note: %% If there is no such window in S that covers all characters in T, return the emtpy string "". %% If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S. min_window() -> "eca" = min_window("cabeca", "cae"), "eca" = min_window("cfabeca", "cae"), "aec" = min_window("cabefgecdaecf", "cae"), "cwae" = min_window("cabwefgewcwaefcf", "cae"), "BANC" = min_window("ADOBECODEBANC", "ABC"), ok. min_window(T, S) -> min_window(T, S, []). min_window([], _T, MinWindow) -> MinWindow; min_window([H | Rest], T, MinWindow) -> NewMinWindow = case lists:member(H, T) of true -> MinWindowFound = fullfill_window(Rest, lists:delete(H, T), [H]), case length(MinWindow) == 0 orelse (length(MinWindow) > length(MinWindowFound) andalso length(MinWindowFound) > 0) of true -> MinWindowFound; false -> MinWindow end; false -> MinWindow end, min_window(Rest, T, NewMinWindow). fullfill_window(_, [], Acc) -> %% window completed Acc; fullfill_window([], _T, _Acc) -> %% no window found ""; fullfill_window([H | Rest], T, Acc) -> %% completing window case lists:member(H, T) of true -> fullfill_window(Rest, lists:delete(H, T), Acc ++ [H]); false -> fullfill_window(Rest, T, Acc ++ [H]) end. 

REF:

Por favor, dê uma olhada nisso também:

 //----------------------------------------------------------------------- bool IsInSet(char ch, char* cSet) { char* cSetptr = cSet; int index = 0; while (*(cSet+ index) != '\0') { if(ch == *(cSet+ index)) { return true; } ++index; } return false; } void removeChar(char ch, char* cSet) { bool bShift = false; int index = 0; while (*(cSet + index) != '\0') { if( (ch == *(cSet + index)) || bShift) { *(cSet + index) = *(cSet + index + 1); bShift = true; } ++index; } } typedef struct subStr { short iStart; short iEnd; short szStr; }ss; char* subStringSmallest(char* testStr, char* cSet) { char* subString = NULL; int iSzSet = strlen(cSet) + 1; int iSzString = strlen(testStr)+ 1; char* cSetBackUp = new char[iSzSet]; memcpy((void*)cSetBackUp, (void*)cSet, iSzSet); int iStartIndx = -1; int iEndIndx = -1; int iIndexStartNext = -1; std::vector subStrVec; int index = 0; while( *(testStr+index) != '\0' ) { if (IsInSet(*(testStr+index), cSetBackUp)) { removeChar(*(testStr+index), cSetBackUp); if(iStartIndx < 0) { iStartIndx = index; } else if( iIndexStartNext < 0) iIndexStartNext = index; else ; if (strlen(cSetBackUp) == 0 ) { iEndIndx = index; if( iIndexStartNext == -1) break; else { index = iIndexStartNext; ss stemp = {iStartIndx, iEndIndx, (iEndIndx-iStartIndx + 1)}; subStrVec.push_back(stemp); iStartIndx = iEndIndx = iIndexStartNext = -1; memcpy((void*)cSetBackUp, (void*)cSet, iSzSet); continue; } } } else { if (IsInSet(*(testStr+index), cSet)) { if(iIndexStartNext < 0) iIndexStartNext = index; } } ++index; } int indexSmallest = 0; for(int indexVec = 0; indexVec < subStrVec.size(); ++indexVec) { if(subStrVec[indexSmallest].szStr > subStrVec[indexVec].szStr) indexSmallest = indexVec; } subString = new char[(subStrVec[indexSmallest].szStr) + 1]; memcpy((void*)subString, (void*)(testStr+ subStrVec[indexSmallest].iStart), subStrVec[indexSmallest].szStr); memset((void*)(subString + subStrVec[indexSmallest].szStr), 0, 1); delete[] cSetBackUp; return subString; } //-------------------------------------------------------------------- 

Edit : aparentemente há um algoritmo O (n) (cf. resposta do algoritmo). Obviamente, isso tem que vencer a linha de base [ingênua] descrita abaixo!

Pena que eu tenho que ir … Eu sou um pouco desconfiado de que podemos conseguir O (n). Vou checar amanhã para ver o vencedor 😉 Divirta-se!

Algoritmo provisório :
A idéia geral é tentar usar sequencialmente um caractere de str2 encontrado em str1 como o início de uma pesquisa (em qualquer uma das duas direções) de todas as outras letras de str2. Mantendo um valor de “duração da melhor correspondência até o momento”, podemos interromper as pesquisas quando elas excederem esse valor. Outras heurísticas provavelmente podem ser usadas para abortar ainda mais as soluções subótimas (até o momento). A escolha da ordem das letras iniciais em str1 é muito importante; sugere-se começar com a (s) letra (s) de str1 que tem a contagem mais baixa e tentar com as outras letras, de uma contagem crescente, em tentativas subseqüentes.

  [loose pseudo-code] - get count for each letter/character in str1 (number of As, Bs etc.) - get count for each letter in str2 - minLen = length(str1) + 1 (the +1 indicates you're not sure all chars of str2 are in str1) - Starting with the letter from string2 which is found the least in string1, look for other letters of Str2, in either direction of str1, until you've found them all (or not, at which case response = impossible => done!). set x = length(corresponding substring of str1). - if (x < minLen), set minlen = x, also memorize the start/len of the str1 substring. - continue trying with other letters of str1 (going the up the frequency list in str1), but abort search as soon as length(substring of strl) reaches or exceed minLen. We can find a few other heuristics that would allow aborting a particular search, based on [pre-calculated ?] distance between a given letter in str1 and some (all?) of the letters in str2. - the overall search terminates when minLen = length(str2) or when we've used all letters of str1 (which match one letter of str2) as a starting point for the search 

Aqui está a implementação do Java

 public static String shortestSubstrContainingAllChars(String input, String target) { int needToFind[] = new int[256]; int hasFound[] = new int[256]; int totalCharCount = 0; String result = null; char[] targetCharArray = target.toCharArray(); for (int i = 0; i < targetCharArray.length; i++) { needToFind[targetCharArray[i]]++; } char[] inputCharArray = input.toCharArray(); for (int begin = 0, end = 0; end < inputCharArray.length; end++) { if (needToFind[inputCharArray[end]] == 0) { continue; } hasFound[inputCharArray[end]]++; if (hasFound[inputCharArray[end]] <= needToFind[inputCharArray[end]]) { totalCharCount ++; } if (totalCharCount == target.length()) { while (needToFind[inputCharArray[begin]] == 0 || hasFound[inputCharArray[begin]] > needToFind[inputCharArray[begin]]) { if (hasFound[inputCharArray[begin]] > needToFind[inputCharArray[begin]]) { hasFound[inputCharArray[begin]]--; } begin++; } String substring = input.substring(begin, end + 1); if (result == null || result.length() > substring.length()) { result = substring; } } } return result; } 

Aqui está o teste do Junit

 @Test public void shortestSubstringContainingAllCharsTest() { String result = StringUtil.shortestSubstrContainingAllChars("acbbaca", "aba"); assertThat(result, equalTo("baca")); result = StringUtil.shortestSubstrContainingAllChars("acbbADOBECODEBANCaca", "ABC"); assertThat(result, equalTo("BANC")); result = StringUtil.shortestSubstrContainingAllChars("this is a test string", "tist"); assertThat(result, equalTo("t stri")); } 
 //[ShortestSubstring.java][1] public class ShortestSubstring { public static void main(String[] args) { String input1 = "My name is Fran"; String input2 = "rim"; System.out.println(getShortestSubstring(input1, input2)); } private static String getShortestSubstring(String mainString, String toBeSearched) { int mainStringLength = mainString.length(); int toBeSearchedLength = toBeSearched.length(); if (toBeSearchedLength > mainStringLength) { throw new IllegalArgumentException("search string cannot be larger than main string"); } for (int j = 0; j < mainStringLength; j++) { for (int i = 0; i <= mainStringLength - toBeSearchedLength; i++) { String substring = mainString.substring(i, i + toBeSearchedLength); if (checkIfMatchFound(substring, toBeSearched)) { return substring; } } toBeSearchedLength++; } return null; } private static boolean checkIfMatchFound(String substring, String toBeSearched) { char[] charArraySubstring = substring.toCharArray(); char[] charArrayToBeSearched = toBeSearched.toCharArray(); int count = 0; for (int i = 0; i < charArraySubstring.length; i++) { for (int j = 0; j < charArrayToBeSearched.length; j++) { if (String.valueOf(charArraySubstring[i]).equalsIgnoreCase(String.valueOf(charArrayToBeSearched[j]))) { count++; } } } return count == charArrayToBeSearched.length; } } 

Esta é uma abordagem usando números primos para evitar um loop e substituí-lo por multiplicações. Várias outras pequenas otimizações podem ser feitas.

  1. Atribua um número primo exclusivo a qualquer um dos caracteres que você deseja encontrar e 1 aos caracteres não interessantes.

  2. Encontre o produto de uma string correspondente multiplicando o número primo pelo número de ocorrências que deveria ter. Agora, este produto só pode ser encontrado se os mesmos fatores primos forem usados.

  3. Pesquise a cadeia desde o início, multiplicando o respectivo número primo à medida que você passa para um produto em execução.

  4. Se o número for maior que a sum correta, remova o primeiro caractere e divida o número primo do produto em execução.

  5. Se o número for menor que a sum correta, inclua o próximo caractere e multiplique-o em seu produto em execução.

  6. Se o número for igual à sum correta, você encontrou uma correspondência, deslize o início e o fim para o próximo caractere e continue procurando outras correspondências.

  7. Decida qual das correspondências é a mais curta.

Essência

 charcount = { 'a': 3, 'b' : 1 }; str = "kjhdfsbabasdadaaaaasdkaaajbajerhhayeom" def find (c, s): Ns = len (s) C = list (c.keys ()) D = list (c.values ()) # prime numbers assigned to the first 25 chars prmsi = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 , 97] # primes used in the key, all other set to 1 prms = [] Cord = [ord(c) - ord('a') for c in C] for e,p in enumerate(prmsi): if e in Cord: prms.append (p) else: prms.append (1) # Product of match T = 1 for c,d in zip(C,D): p = prms[ord (c) - ord('a')] T *= p**d print ("T=", T) t = 1 # product of current string f = 0 i = 0 matches = [] mi = 0 mn = Ns mm = 0 while i < Ns: k = prms[ord(s[i]) - ord ('a')] t *= k print ("testing:", s[f:i+1]) if (t > T): # included too many chars: move start t /= prms[ord(s[f]) - ord('a')] # remove first char, usually division by 1 f += 1 # increment start position t /= k # will be retested, could be replaced with bool elif t == T: # found match print ("FOUND match:", s[f:i+1]) matches.append (s[f:i+1]) if (i - f) < mn: mm = mi mn = i - f mi += 1 t /= prms[ord(s[f]) - ord('a')] # remove first matching char # look for next match i += 1 f += 1 else: # no match yet, keep searching i += 1 return (mm, matches) print (find (charcount, str)) 

(nota: esta resposta foi originalmente postada em uma pergunta duplicada, a resposta original foi excluída.)

Implementação C #:

 public static Tuple FindMinSubstringWindow(string input, string pattern) { Tuple windowCoords = new Tuple(0, input.Length - 1); int[] patternHist = new int[256]; for (int i = 0; i < pattern.Length; i++) { patternHist[pattern[i]]++; } int[] inputHist = new int[256]; int minWindowLength = int.MaxValue; int count = 0; for (int begin = 0, end = 0; end < input.Length; end++) { // Skip what's not in pattern. if (patternHist[input[end]] == 0) { continue; } inputHist[input[end]]++; // Count letters that are in pattern. if (inputHist[input[end]] <= patternHist[input[end]]) { count++; } // Window found. if (count == pattern.Length) { // Remove extra instances of letters from pattern // or just letters that aren't part of the pattern // from the beginning. while (patternHist[input[begin]] == 0 || inputHist[input[begin]] > patternHist[input[begin]]) { if (inputHist[input[begin]] > patternHist[input[begin]]) { inputHist[input[begin]]--; } begin++; } // Current window found. int windowLength = end - begin + 1; if (windowLength < minWindowLength) { windowCoords = new Tuple(begin, end); minWindowLength = windowLength; } } } if (count == pattern.Length) { return windowCoords; } return null; } 

Código Java para a abordagem discutida acima:

 private static Map frequency; private static Set charsCovered; private static Map encountered; /** * To set the first match index as an intial start point */ private static boolean hasStarted = false; private static int currentStartIndex = 0; private static int finalStartIndex = 0; private static int finalEndIndex = 0; private static int minLen = Integer.MAX_VALUE; private static int currentLen = 0; /** * Whether we have already found the match and now looking for other * alternatives. */ private static boolean isFound = false; private static char currentChar; public static String findSmallestSubStringWithAllChars(String big, String small) { if (null == big || null == small || big.isEmpty() || small.isEmpty()) { return null; } frequency = new HashMap(); instantiateFrequencyMap(small); charsCovered = new HashSet(); int charsToBeCovered = frequency.size(); encountered = new HashMap(); for (int i = 0; i < big.length(); i++) { currentChar = big.charAt(i); if (frequency.containsKey(currentChar) && !isFound) { if (!hasStarted && !isFound) { hasStarted = true; currentStartIndex = i; } updateEncounteredMapAndCharsCoveredSet(currentChar); if (charsCovered.size() == charsToBeCovered) { currentLen = i - currentStartIndex; isFound = true; updateMinLength(i); } } else if (frequency.containsKey(currentChar) && isFound) { updateEncounteredMapAndCharsCoveredSet(currentChar); if (currentChar == big.charAt(currentStartIndex)) { encountered.put(currentChar, encountered.get(currentChar) - 1); currentStartIndex++; while (currentStartIndex < i) { if (encountered.containsKey(big.charAt(currentStartIndex)) && encountered.get(big.charAt(currentStartIndex)) > frequency.get(big .charAt(currentStartIndex))) { encountered.put(big.charAt(currentStartIndex), encountered.get(big.charAt(currentStartIndex)) - 1); } else if (encountered.containsKey(big.charAt(currentStartIndex))) { break; } currentStartIndex++; } } currentLen = i - currentStartIndex; updateMinLength(i); } } System.out.println("start: " + finalStartIndex + " finalEnd : " + finalEndIndex); return big.substring(finalStartIndex, finalEndIndex + 1); } private static void updateMinLength(int index) { if (minLen > currentLen) { minLen = currentLen; finalStartIndex = currentStartIndex; finalEndIndex = index; } } private static void updateEncounteredMapAndCharsCoveredSet(Character currentChar) { if (encountered.containsKey(currentChar)) { encountered.put(currentChar, encountered.get(currentChar) + 1); } else { encountered.put(currentChar, 1); } if (encountered.get(currentChar) >= frequency.get(currentChar)) { charsCovered.add(currentChar); } } private static void instantiateFrequencyMap(String str) { for (char c : str.toCharArray()) { if (frequency.containsKey(c)) { frequency.put(c, frequency.get(c) + 1); } else { frequency.put(c, 1); } } } public static void main(String[] args) { String big = "this is a test string"; String small = "tist"; System.out.println("len: " + big.length()); System.out.println(findSmallestSubStringWithAllChars(big, small)); } 
 def minimum_window(s, t, min_length = 100000): d = {} for x in t: if x in d: d[x]+= 1 else: d[x] = 1 tot = sum([y for x,y in d.iteritems()]) l = [] ind = 0 for i,x in enumerate(s): if ind == 1: l = l + [x] if x in d: tot-=1 if not l: ind = 1 l = [x] if tot == 0: if len(l)