2

文字列Sと文字列Tが与えられた場合、複雑さO（n）のTのすべての文字を含むSの最小ウィンドウを見つけます。

例えば、

S = "ADOBECODEBANC"
T = "ABC"

最小ウィンドウは"BANC"です。

void getstring(char str1[],char str2[],char hash[])
{

    int len=strlen(str1);
    int i=0,j;              //i keeps the previous index
    int min=INT_MAX;
    int cnt=0;  
    for(j=0;j<len;j++)
        {
            if(hash[str1[j]]==-1)   //means uninitialized, will be checked for first time only
            {

                cnt++;              
                hash[str1[j]]=j;                    

                if(cnt==1)
                i=j;

                int y=check(hash,str2); //checking for the characters
                //printf("y=%d",y);
                if(y)       //means all the characters are present
                {
                    if( (j-i+1)<min)
                    {
                    min=j-i+1;
                    I=i;
                    J=j;
                    }               


                }


               }
                else if(hash[str1[j]]>=0)
                {


                    hash[str1[j]]=j;



                    if(check(hash,str2) )
                    {                   

                    if( hash[str1[i]]==hash[str1[j]] )      //it means that we are moving the first
                    {                       //index only
                    i=getmin(hash,str2);    //get minimum index of the element              

                        if( (j-i+1)<min)
                        {
                            min=j-i+1;
                            I=i;
                            J=j;
                        }


                    }
                    //else
                    }
                    else
                    {
                    if( hash[str1[i]]==hash[str1[j]] )
                    i=hash[str1[i]];                        
                    }

                }//end of else-if
                }//end of for    
}

ハッシュを使用してコードを作成しました。つまり、文字列Tの文字のインデックス値をハッシュに保持し、2つのインデックスを使用しています。最初に、下位のインデックスの文字と同じ文字を取得するとすぐに、長さを確認してから、インデックスを更新してください。

このアプローチでは、最悪の場合O（nk）が必要になります。

n - is the number of characters in S
k - is the number of characters in T

O(n)この問題に時間がかかるアプローチはありますか？

4

2 に答える 2

3

したがって、Tの各文字を最後に見たのはいつかを追跡するSのパスを作成します。

各ポイントで、最後に表示された文字の最も遠い方がウィンドウの左端を区切ります（現在のポイントが右端になります）。

これらのウィンドウのうち、これまでに見た最小のウィンドウを追跡するだけです。アルゴリズムの最後では、これが全体として最小のウィンドウになります。

于 2012-06-02T22:12:42.627 に答える
0

これがすべてのテストケースに合格した私のJavaコードです。それがあなたにも役立つことを願っています。

public class Solution {
    public String minWindow(String s, String t) {

         if(t.length()>s.length()) 
        return "";
    String result = "";

     HashMap <Character, Integer> shouldFind = new HashMap<Character, Integer>();
     HashMap <Character, Integer> hasFound = new HashMap<Character, Integer>();
     int count =0, j=0,  minWindow = s.length()+1, start=0, finish =0;

     Integer sLength = s.length();
     Integer tLength = t.length();

     for(int i = 0 ; i < tLength ; i++)
     {
         char tChar = t.charAt(i);
         if(!shouldFind.containsKey(tChar))
         shouldFind.put(tChar,1);
         else 
         shouldFind.put (tChar ,shouldFind.get(tChar)+1);

     }


     for (int i =0; i <sLength; i ++)
     {
         char sChar = s.charAt(i);

         if(shouldFind.containsKey(sChar))
         {
             if(!hasFound.containsKey(sChar)){
             hasFound.put(sChar, 1);
             count++;
             }
             else {
                 if(hasFound.get(sChar) < shouldFind.get(sChar) )
                 count ++;

             hasFound.put(sChar, hasFound.get(sChar) +1);

             }
         }




        if(count == tLength)
        {
            char ch = s.charAt(j);

          while (!hasFound.containsKey(ch) || hasFound.get(ch) > shouldFind.get(ch))
          {
              if(hasFound.containsKey(ch) && hasFound.get(ch)>shouldFind.get(ch))
              hasFound.put(ch , hasFound.get(ch) -1);

              j++;
              ch = s.charAt(j);
          }

            //lets find the minimum window
            if(minWindow > (i-j+1) )
            {
                minWindow = i - j + 1;
                start = j;
                finish = i+1;
                result = s.substring(start, finish);

            }

        }}




        return result;
    }}
于 2015-09-06T08:10:05.367 に答える