Comment trouver le plus petit sous-chaîne qui contient tous les caractères d'une chaîne de caractères?

J'ai récemment rencontré une question intéressante sur les cordes. Supposons que vous êtes donné des éléments suivants:

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

Donc, étant donné ci-dessus, comment puis-je m'approche vers la recherche de la plus petite sous-chaîne de chaîne1 qui contient tous les caractères de la chaîne 2?

  • Devrait chaîne2 être rist ou tisr? Et dans ce cas ne serait pas la sortie "st str"?
  • mot2 est donné comme "tiste" et qu'il devrait être. Si vous dites "rist" ou "tisr" que votre réponse "st str" ne contient pas "je".
  • Oh, je vois, je pensais que le " r " a été mal puisqu'il n'était pas dans chaîne2 mais vous dites qu'elle doit contenir tous de string2, mais peuvent également contenir d'autres lettres...
  • oui, exactement!
  • faire des doublons dans string2 doivent être pris en compte ainsi? parce que sinon la plus courte chaîne ayant tist dans string1 est this ou stri
InformationsquelleAutor Rajendra Uppal | 2010-03-17
  1. 33

    Vous pouvez faire un histogramme de balayage dans O(N+M) temps et O(1) espace où N est le nombre de caractères dans la première chaîne et M est le nombre de caractères dans la seconde.

    Il fonctionne comme ceci:

    • Faire un histogramme de la deuxième chaîne de caractères (touche de fonctionnement est hist2[ s2[i] ]++).
    • Faire un histogramme cumulatif de la première chaîne de caractères jusqu'à ce que l'histogramme contient tous les caractères qui la deuxième chaîne de l'histogramme contient (que j'appellerai "l'histogramme de la condition").
    • Puis aller de l'avant sur la première chaîne, en soustrayant de l'histogramme, jusqu'à ce qu'il ne parvient pas à répondre à l'histogramme de l'état. Marque bits de la première chaîne (avant le déménagement final) que votre tentative de sous-chaîne.
    • Déplacer le devant de la sous-chaîne transmet à nouveau jusqu'à ce que vous rencontrer l'histogramme condition encore. Déplacez la fin transfère jusqu'à ce qu'il échoue à nouveau. Si c'est une sous-chaîne plus courte que la première, marque que votre tentative de sous-chaîne.
    • Répétez jusqu'à ce que vous avez passé à travers l'ensemble de la première chaîne.
    • La nette sous-chaîne est votre réponse.

    Noter qu'en variant la case que vous utilisez sur l'histogramme condition, vous pouvez choisir d'avoir le même jeu de caractères que la deuxième chaîne, ou au moins autant de caractères de chaque type. (C'est juste la différence entre a[i]>0 && b[i]>0 et a[i]>=b[i].)

    Vous pouvez accélérer l'histogramme vérifie si vous gardez une trace de la condition n'est pas satisfaite lorsque vous essayez de le satisfaire, et de vérifier que la chose que vous décrémenter quand vous êtes à essayer de le casser. (Sur l'accumulation initiale, vous comptez combien d'articles que vous avez satisfait, et l'augmentation de compter chaque fois que vous ajoutez un nouveau personnage qui prend la condition de false à true.)

    • +1: C'est beaucoup plus lisible que python. Ce serait bien si vous avez inclus une preuve/explication de pourquoi cela fonctionne aussi.
    • Kerr: je ne vois pas en quoi c'est O(1) de l'espace. Votre histogrammes pas de O(N+M) l'espace si tous les caractères sont uniques (pire des cas)?
    • O(M) de l'espace qui peut être fait (plutôt que de O(N+M)), que vous n'avez pas vraiment besoin de vous soucier de caractères qui ne sont pas présents est s2. Je suis d'accord cependant, que l'utilisation de l'espace est en O(1) semble incorrect et ne semble pas correspondre à la description.
    • Je pense que nous savons tous ce que O(1) signifie. Il vous manque le point, et la preuve de la demande n'était pas de savoir pourquoi il est O(N), c'est pourquoi il est correct. Si vous le souhaitez, je peux l'ajouter à votre post.
    • Vous êtes complètement à droite. J'étais juste en suivant les étapes de l'algorithme et de ne pas profiter de cette (simple) d'optimisation en compte. @Rex Kerr: à Partir d'un point de vue théorique, je crois que vous avez tort. Si vous allouer une quantité constante de mémoire, je peux choisir M assez grand pour que vos compteurs de débordement, de sorte que nous aurions besoin d'au moins O(log_2(M)) de l'espace. Plus pragmatique, l'utilisation de la notation, je voudrais également envisager de O(1) pour être un peu trompeur, car on associe habituellement avec un petit montant fixe de la mémoire. Pouvons-nous nous contenter de O(min(jeu de caractères de taille, M)) 🙂
    • Pourquoi ne pas ajouter votre propre réponse sur pourquoi il est/n'est pas correct, puisque les deux algorithmist et j'ai la même réponse (comme la solution à la fin de nvl du lien)? @Mads: Bon point--disons O(|set(M)|) peut-être, où |set(M)| est le nombre de caractères dans M.
    • Je ne prétends pas qu'il est incorrect. Je lui ai donné un +1 déjà (c'est à dire je pense que c'est correct). Je ne vois vraiment pas l'intérêt d'avoir plusieurs réponses par dire la même chose de différentes façons ou d'une réponse complétant l'autre. Ce site est destiné à répondre à des questions, de ne pas noyer l'interlocuteur avec beaucoup de réponses diverses disant des choses similaires. Je vous suggère d'ajouter une preuve pour faire de votre réponse plus complète (et mieux), pas à remettre en question l'exactitude. Vous ne semblez pas à obtenir le point de ce site... de toute façon, j'en ai fini avec cette conversation.

    InformationsquelleAutor Rex Kerr
  2. 40

    Pour voir plus de détails, y compris le code de travail, vérifiez mon blog à:

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

    Pour aider à illustrer cette approche, j'ai un exemple: mot1 = "acbbaca" et string2 = "aba". Ici, nous utilisons également le terme de "fenêtre", ce qui signifie un bloc contigu de caractères à partir de mot1 (pourrait être interchangeable avec le terme de sous-chaîne).

    Comment trouver le plus petit sous-chaîne qui contient tous les caractères d'une chaîne de caractères?

    i) string1 = "acbbaca" et string2 = "aba".

    Comment trouver le plus petit sous-chaîne qui contient tous les caractères d'une chaîne de caractères?

    ii) Le premier minimum fenêtre est trouvé.
    Notez que nous ne pouvons pas avancer de commencer
    pointeur comme hasFound['a'] ==
    needToFind['a'] == 2. L'avancement serait
    signifie la rupture de la contrainte.

    Comment trouver le plus petit sous-chaîne qui contient tous les caractères d'une chaîne de caractères?

    iii) La deuxième fenêtre est trouvé. commencer
    pointeur pointe encore à la première
    l'élément "a". hasFound['a'] (3) est
    plus de needToFind['a'] (2). Nous
    décrémenter hasFound['a'] par l'un et
    l'avance de commencer pointeur vers la droite.

    Comment trouver le plus petit sous-chaîne qui contient tous les caractères d'une chaîne de caractères?

    iv) Nous ignorer 'c', car il n'est pas trouvé
    dans chaîne2. Commencer pointeur pointe désormais à "b".
    hasFound['b'] (2) est supérieure à
    needToFind['b'] (1). Nous décrémenter
    hasFound['b'] par l'un et l'avance de commencer
    pointeur vers la droite.

    Comment trouver le plus petit sous-chaîne qui contient tous les caractères d'une chaîne de caractères?

    v) Commencer pointeur pointe désormais à la
    côté "b". hasFound['b'] (1) est égal
    pour needToFind['b'] (1). Nous nous arrêtons
    immédiatement et c'est notre nouveau
    trouvé minimale d'une fenêtre.

    L'idée est basée principalement sur l'aide de deux pointeurs (de début et de fin de la position de la fenêtre) et de deux tables (needToFind et hasFound) en traversant chaîne1. needToFind stocke le nombre total de caractères dans mot2 et hasFound stocke le nombre total d'un personnage rencontré jusqu'à présent. Nous utilisons également un nombre variable pour stocker le nombre de caractères dans chaîne2 qui a rencontré jusqu'à présent (pas de comptage de caractères où hasFound[x] dépasse needToFind[x]). Lorsque le comte est égal à chaîne2 longueur, nous savons qu'une fenêtre valide est trouvé.

    Chaque fois que l'on avance la fin pointeur vers un élément x), on incrémente hasFound[x] par un. Nous avons également incrémenter compteur d'une unité si hasFound[x] est inférieure ou égale à needToFind[x]. Pourquoi? Lorsque la contrainte est satisfaite (c'est-count est égal à chaîne2 de la taille), nous avons immédiatement commencer à l'avance du curseur de droite que possible, tout en maintenant la contrainte.

    Comment vérifier si c'est le maintien de la contrainte? Supposons que commencer pointe vers un élément x, on vérifie si hasFound[x] est plus grand que needToFind[x]. Si elle l'est, on peut décrémenter hasFound[x] par l'un et l'avancement de commencer pointeur sans casser la contrainte. Sur l'autre main, si elle n'est pas, nous nous arrêtons immédiatement au titre de l'avancement de commencer pointeur brise la fenêtre de contrainte.

    Enfin, on vérifie si le minimum de la longueur de la fenêtre est moins que le minimum actuel. Mise à jour le minimum si un nouveau minimum est trouvé.

    Essentiellement, l'algorithme trouve la première fenêtre qui satisfait à la contrainte, puis continuer à maintenir la contrainte tout au long de.

    • Je pense que l'approche doit être plus propre explication. En particulier, les termes comme "hasFound" et "needToFind'. Il est difficile pour envelopper ma tête autour de lui.
    InformationsquelleAutor 1337c0d3r
  3. 6

    Voici un O(n) solution. L'idée de base est simple: pour chaque indice de départ, trouver le moins que l'index de fin, tels que la sous-chaîne contient toutes les lettres. Le truc, c'est que le moins se terminant augmentation de l'indice au cours de la fonction, donc avec un peu de support de structure de données, nous considérons que chaque personnage au plus deux fois.

    En 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
    • Je n'ai pas travaillé en Python, mais je peux en trouver un pour...tandis que la boucle ne semble pas O(n). Pouvez vous s'il vous plaît dites à votre approche en prenant l'exemple donné dans la question, serait apprécié.
    • j ne peut qu'augmenter len(s1) fois, de sorte que la boucle while ne O(n) de travail au total.
    • Cet algorithme est exactement ce que j'ai décrit dans mon post, si cela aide--i marques de la queue de la sous-chaîne et j marques de la tête. @algorithmist: beau travail, à venir avec code toujours aussi légèrement plus vite que je suis venu avec une description!
    • Ce n'est PAS O(n) la solution! Parce que la recherche dans le dictionnaire lui-même a le pire des cas de complexité O(n) en.wikipedia.org/wiki/..., de sorte que plusieurs votre n au moins par 2
    InformationsquelleAutor user287792
  4. 2

    J'ai reçu la même question de l'entrevue. Je suis une C++ candidats, mais j'étais dans une position de code relativement rapide en JAVA.

    Java [Avec L'Aimable Autorisation De 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<p.length();i++) {
            pCount[(int)(p.charAt(i))]++;
            sCount[(int)(s.charAt(i))]++;
        }
        int i = 0, j = p.length(), min = Integer.MAX_VALUE;
        String res = null;
        //Time: O(s.lenght)
        while (j < s.length()) {
            if (containsPatternChar(sCount, pCount)) {
                if ((j - i) < min) {
                    min = j - i;
                    res = s.substring(i, j);
                    //This is the smallest possible substring.
                    if(min==p.length())
                        break;
                    //Reduce the window size.
                    sCount[(int)(s.charAt(i))]--;
                    i++;
                }
            } else {
                sCount[(int)(s.charAt(j))]++;
                //Increase the window size.
                j++;
            }
        }
        System.out.println(res);
        return res;
    }
}

    C++ [avec l'aimable autorisation de sundeepblue]

    #include <iostream>
#include <vector>
#include <string>
#include <climits>
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<int> total(256, 0);
    vector<int> sofar(256, 0);
    for(int i=0; i<nt; i++) 
        total[t[i]]++;

    int L = 0, R; 
    int minL = 0;                           //gist2
    int count = 0;
    int min_win_len = INT_MAX;

    for(R=0; R<ns; R++) {                   //gist0, a big for loop
        if(total[s[R]] == 0) continue;
        else sofar[s[R]]++;

        if(sofar[s[R]] <= total[s[R]])      //gist1, <= not <
            count++;

        if(count == nt) {                   //POS1
            while(true) {
                char c = s[L]; 
                if(total[c] == 0) { L++; }
                else if(sofar[c] > 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 [avec l'aimable autorisation de 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:

    InformationsquelleAutor jackdaniel
  5. 1

    Jetez un oeil à ceci: les

    //-----------------------------------------------------------------------

bool IsInSet(char ch, char* cSet)
{
    char* cSetptr = cSet;
    int index = 0;
    while (*(cSet+ index) != '
    //-----------------------------------------------------------------------
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<ss> 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;
}
//--------------------------------------------------------------------

    ')
    {
        if(ch == *(cSet+ index))
        {
            return true;            
        }
        ++index;
    }
    return false;
}

void removeChar(char ch, char* cSet)
{
    bool bShift = false;
    int index = 0;
    while (*(cSet + index) != '
    //-----------------------------------------------------------------------
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<ss> 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;
}
//--------------------------------------------------------------------

    ')
    {
        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<ss> subStrVec;
    int index = 0;

    while( *(testStr+index) != '
    //-----------------------------------------------------------------------
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<ss> 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;
}
//--------------------------------------------------------------------

    ' )
    {
        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;
}
//--------------------------------------------------------------------
    InformationsquelleAutor Manish Kumar
  6. 0

    Modifier: apparemment il y a un algorithme O(n) (cf. algorithmist de réponse). Évidemment, cela avoir cette volonté de battre l' [naïf] de référence décrit ci-dessous!

    Trop mal je dois y aller... je suis un peu méfiant que nous pouvons obtenir de O(n). Je vais vérifier demain pour voir les gagnants 😉 amusez-vous!

    Provisoire algorithme:

    L'idée générale est de manière séquentielle essayer et utiliser un caractère de str2 trouvé dans str1 comme le début d'une recherche (dans les deux/les deux directions) de toutes les autres lettres de str2. En gardant une "longueur de correspondre au mieux à la mesure de la" valeur, nous pouvons abandonner les recherches lorsqu'ils dépassent cette. D'autres heuristiques peut probablement être utilisé pour annuler sous-optimale (jusqu'à présent) des solutions. Le choix de l'ordre de départ des lettres dans str1 choses encore; il est suggéré de commencer avec la lettre(s) de str1 qui ont la plus faible compter et à essayer avec les autres lettres, une augmentation de compter, dans les tentatives ultérieures.

      [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
    InformationsquelleAutor mjv
  7. 0

    Ici est l'implémentation 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;
}

    Voici le Test 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"));
}
    InformationsquelleAutor craftsmannadeem
  8. 0
    //[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;
}
}
    • Bien que ce code peut aider à résoudre le problème, fournir plus de contexte sur pourquoi et/ou comment il répond à la question permettrait d'améliorer de manière significative sa valeur à long terme. Veuillez modifier votre réponse à ajouter quelques explications.
    InformationsquelleAutor Shashank
  9. 0

    C'est une approche à l'aide de nombres premiers pour éviter une boucle, et de le remplacer avec les multiplications. Plusieurs autres optimisations mineures peuvent être apportées.

    1. Attribuer un unique nombre premier de l'un des personnages que vous souhaitez trouver, et 1 à la inintéressant caractères.

    2. Trouver le produit d'une chaîne correspondante en multipliant le nombre premier avec le nombre d'occurrences qu'elle doit avoir. Maintenant, ce produit ne peut être trouvée que si les mêmes facteurs premiers sont utilisés.

    3. De la recherche la chaîne de caractères à partir du début, en multipliant les respectifs le premier numéro que vous vous déplacez dans l'exécution d'un produit.

    4. Si le nombre est plus grand que le bon somme, supprimer le premier caractère et de diviser son premier numéro de votre produit.

    5. Si le nombre est inférieur à la bonne somme, inclure le caractère suivant et de se multiplier dans votre produit.

    6. Si le nombre est le même que le bon somme que vous avez trouvé une correspondance, faites glisser début et à la fin au caractère suivant et continuer à chercher pour les autres matches.

    7. Décider laquelle des matches est le plus court.

    Gist

    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))

    (note: cette réponse a été posté à une double question, la réponse originale à cette question est maintenant supprimé.)

    InformationsquelleAutor gauteh
  10. 0

    C# De Mise En Œuvre:

    public static Tuple<int, int> FindMinSubstringWindow(string input, string pattern)
{
Tuple<int, int> windowCoords = new Tuple<int, int>(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<int, int>(begin, end);
minWindowLength = windowLength;
}
}
}
if (count == pattern.Length)
{
return windowCoords;
}
return null;
}
    InformationsquelleAutor shlatchz
  11. 0

    J'ai mis en place à l'aide de Python3 en O(N) efficacité:

    def get(s, alphabet="abc"):
seen = {}
for c in alphabet:
seen[c] = 0
seen[s[0]] = 1
start = 0
end = 0
shortest_s = 0
shortest_e = 99999
while end + 1 < len(s):
while seen[s[start]] > 1:
seen[s[start]] -= 1
start += 1
# Constant time check:
if sum(seen.values()) == len(alphabet) and all(v == 1 for v in seen.values()) and \
shortest_e - shortest_s > end - start:
shortest_s = start
shortest_e = end
end += 1
seen[s[end]] += 1
return s[shortest_s: shortest_e + 1]
print(get("abbcac")) # Expected to return "bca"
    InformationsquelleAutor TheLogicGuy
  12. 0
        String s = "xyyzyzyx";
String s1 = "xyz";
String finalString ="";
Map<Character,Integer> hm = new HashMap<>();
if(s1!=null && s!=null && s.length()>s1.length()){
for(int i =0;i<s1.length();i++){
if(hm.get(s1.charAt(i))!=null){
int k = hm.get(s1.charAt(i))+1;
hm.put(s1.charAt(i), k);
}else
hm.put(s1.charAt(i), 1);
}
Map<Character,Integer> t = new HashMap<>();
int start =-1;
for(int j=0;j<s.length();j++){
if(hm.get(s.charAt(j))!=null){
if(t.get(s.charAt(j))!=null){
if(t.get(s.charAt(j))!=hm.get(s.charAt(j))){
int k = t.get(s.charAt(j))+1;
t.put(s.charAt(j), k);
}
}else{
t.put(s.charAt(j), 1);
if(start==-1){
if(j+s1.length()>s.length()){
break;
}
start = j;
}
}
if(hm.equals(t)){
t = new HashMap<>();
if(finalString.length()<s.substring(start,j+1).length());
{
finalString=s.substring(start,j+1);
}
j=start;
start=-1;                       
}
}
}
    • Pourriez-vous nous expliquer les pourquoi et comment votre extrait de code fournit une réponse à la question? Je vous remercie.
    • Je suis l'aide de deux HashMaps pour stocker le nombre de caractère de chaque chaîne et vérifier si deux cartes sont égales , si les deux cartes sont égales nous avons ensuite le sous-chaînes dans une chaîne donnée.
    InformationsquelleAutor Sai Chand
  13. 0

    JavaScript solution en bruteforce façon:

    JS:

    function shortestSubStringOfUniqueChars(s){
var uniqueArr = [];
for(let i=0; i<s.length; i++){
if(uniqueArr.indexOf(s.charAt(i)) <0){
uniqueArr.push(s.charAt(i));
}
}
let windoww = uniqueArr.length;
while(windoww < s.length){
for(let i=0; i<s.length - windoww; i++){
let match = true;
let tempArr = [];
for(let j=0; j<uniqueArr.length; j++){
if(uniqueArr.indexOf(s.charAt(i+j))<0){
match = false;
break;
}
}
let checkStr
if(match){
checkStr =  s.substr(i, windoww);
for(let j=0; j<uniqueArr.length; j++){
if(uniqueArr.indexOf(checkStr.charAt(j))<0){
match = false;
break;
}
}
}
if(match){
return checkStr;
}
}
windoww = windoww + 1;
}
}
console.log(shortestSubStringOfUniqueChars("ABA"));

    InformationsquelleAutor ganesh phirke
  14. -1

    Code Java pour l'approche discuté ci-dessus:

    private static Map<Character, Integer> frequency;
private static Set<Character> charsCovered;
private static Map<Character, Integer> 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<Character, Integer>();
instantiateFrequencyMap(small);
charsCovered = new HashSet<Character>();
int charsToBeCovered = frequency.size();
encountered = new HashMap<Character, Integer>();
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));
}
    InformationsquelleAutor Bhumik Thakkar
  15. -1
    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)<min_length:
min_length = len(l)
min_length = minimum_window(s[i+1:], t, min_length)
return min_length
l_s = "ADOBECODEBANC"
t_s = "ABC"
min_length = minimum_window(l_s, t_s)
if min_length == 100000:
print "Not found"
else:
print min_length
    InformationsquelleAutor SidML