В этом посте мы обсудим, как решить проблему с минимальной оконной подстрокой, используя принцип скользящего окна.
Описание проблемы:
Для строки S и строки T найдите минимальное окно в S, которое будет содержать все символы из T со сложностью O (n).
Пример:
Ввод: S = «ADOBECODEBANC», T = «ABC».
Выход: «БАНК»
Примечание. Если в S нет такого окна, которое покрывает все символы в T, верните пустую строку «».
Если такое окно есть, гарантируется, что в S. всегда будет только одно уникальное минимальное окно.
Пошаговое решение проблемы:
Поскольку в этой задаче мы должны найти минимальное окно, первая парадигма, которая приходит нам в голову для решения этой проблемы, - это скользящее окно.
Базовый случай:
если s или t равны нулю, мы не можем найти между ними общего окна.
if(s==null || t==null) return “”;
Основной алгоритм:
сначала давайте сохраним все количество символов t на карте, как показано ниже, чтобы мы могли легко проверить доступность персонажа с этой карты в O (1).
int[] map=new int[128]; for(Character c:t.toCharArray())map[c]++;
Давайте возьмем два указателя start и end для итерации по s и инициализируем их 0 вместе с некоторыми другими переменными.
int start = 0, end = 0, minStart = 0, minLen = Integer.MAX_VALUE, counter = t.length();
Теперь мы перебираем s, используя конечный указатель, и проверяем, присутствует ли текущий символ в t или нет, проверяя map [arr [end]] ›0. Если он присутствует, уменьшаем значение счетчика, чтобы указать, что он у нас есть. соответствие символа и символ (count-1), который необходимо сопоставить. Также мы уменьшаем map [arr [end]], чтобы указать, что мы прошли текущий символ, используя конечный указатель.
В этом процессе, если мы получаем count == 0, это означает, что мы получили желаемое окно, поэтому замените это окно как окно результата, если это минимальное окно.
Теперь мы увеличиваем map [arr [start]], чтобы восстановить счетчик символов на карте и обозначать, что мы закончили с arr [start], и перемещаем start указатель вперед, чтобы удалить начало из текущего окна.
Здесь следует отметить две важные вещи:
1. if (map[arr[end]] > 0) counter — ; end++;
это означает, что мы получили совпадение char в s с char в t, поэтому у нас есть counter-1 char для сопоставления в текущем окне.
2. if(map[arr[start]]>0)counter++; start++;
это означает, что после восстановления фактического счетчика символов в карте путем перехода через указатель начала, если счетчик> 0, тогда счетчик увеличивается и начинается, поскольку мы удаляем этот символ из текущего окна и перемещаем окно вперед.
Полный код этой проблемы можно найти в https://github.com/GyanTech877/algorithms/blob/master/slidingwindow/SlidingWindowMaximum.java.
Удачного обучения 😎