Найдите длину наименьшей подстроки, которая содержит другую строку в качестве подпоследовательности - PullRequest
Новая
       26

Найдите длину наименьшей подстроки, которая содержит другую строку в качестве подпоследовательности

0 голосов
/ 05 мая 2020

Допустим, у меня есть строка s1 = "eabegcghdefgh" и другая строка s2 = "egh".

Код должен возвращать ответ 4 из-за подстроки "efgh" из s1 (поскольку это наименьшая подстрока, содержащая s2 в качестве подпоследовательности).

Примечание: Может быть несколько возможных подстрок, но "efgh" - наименьшая такая подстрока.

Другими словами, найти длина наименьшей подстроки s1, которая содержит все символы другой строки s2, но по порядку.

Обратите внимание: я хочу спросить, как это сделать при временной сложности O (n).

1 Ответ

0 голосов
/ 12 мая 2020

Это основная c проблема со скользящим окном, часто известная как «Наименьшее окно в строке, содержащей все символы другой строки». Мы подходим к этой проблеме, имея два указателя «низкий» и «высокий», начинающиеся с первого индекса строки, в которой будет выполняться поиск, и мы увеличиваем высокий указатель до тех пор, пока все символы шаблона не будут сопоставлены, а затем мы пытаемся сжать подстроку на увеличивая нижний указатель.

Вот фрагмент java проблемы. 

 public static String smallestWindow(String s, String pat){
    if(s == null || s.length() == 0)return "-1";
    int map[] = new int[128];
for(char k : pat.toCharArray())
map[k]++;
int count =0,start=-1,end=-1,lo=0,hi=0,min= Integer.MAX_VALUE;

for(hi = 0;hi<s.length();hi++)
{
    if(map[s.charAt(hi)] >0)
     count++;

     map[s.charAt(hi)]--;

     if(count == pat.length())
     {
         while(lo<hi && map[s.charAt(lo)] <0)
         { map[s.charAt(lo)]++;
             lo++;
         }
         if(min > hi - lo +1)
         {
             min = hi - lo+1;
             start = lo;
             end = hi+1;
         }
         map[s.charAt(lo)]++;

         lo++;
         count--; 
     }
}
return start == -1? "-1" : s.substring(start,end);
}

Я рекомендую вам посмотреть это видео, чтобы хорошо понять его. Наименьшее окно в строке, содержащей все символы другой строки

...