Сегодня в этом блоге я объясню алгоритм решения самой длинной подстроки без повторения символов, используя технику наивного и скользящего окна.
Совет для новичков: попробуйте решить задачу последовательно на листе бумаги, используя разные методы, пока не придете к разумному решению. Большинство новичков тратят много энергии на написание идеального кода и не понимают, что копирование мыслительного процесса с бумаги на компьютер - лишь минутная часть улучшения в программировании. Не забывайте проявлять терпение и не сдаваться.
Учитывая строку str
, мы должны найти длину самой длинной подстроки без каких-либо повторений. Например,
if str = "abcabcbb" 3 (because "abc" is the longest substring with no repetitions)
Наивный подход заключался бы в проверке всех подстрок и проверке на каждой i-й итерации, существует ли повторяющийся символ. Пусть начальный и конечный индексы подстроки равны i and j where 0 ≤ i < j ≤ n
. Переберите все символы и проверьте, существует ли новый проанализированный символ в подстроке. Чтобы проверить дублирование, создайте function checkDuplicacy
, который создает набор из подстроки и проходит через него, чтобы вернуть истину или ложь.
Следовательно, используя два вложенных цикла с i от 0 до n −1 и j от i +1 до n, мы можем перечислить все подстроки s
. Ниже приведен код наивного подхода:
int lenOfLongestSubstring(string s) { int n = s.length(); int ans = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (checkDuplicacy(s, i, j)) res = max(res, j - i + 1); } } return ans; } bool checkDuplicacy(string& s, int start, int end) { vector<int> chars(128); for (int i = start; i <= end; i++) { char c = s[i]; chars[c]++; if (chars[c] > 1) return false; } return true; }
Этот подход требует O(n³)
времени, но мы можем добиться большего, используя метод скользящего окна.
Техника скользящего окна показывает, как вложенный цикл for в некоторых задачах можно преобразовать в один цикл for, чтобы уменьшить временную сложность.
В наивных подходах мы неоднократно проверяем подстроку, чтобы увидеть, есть ли в ней повторяющийся символ. Но в этом нет необходимости. Если подстрока s_ij от индекса i до j −1 уже проверена на отсутствие повторяющихся символов. Нам нужно только проверить, есть ли уже s [j] в подстроке s_ij.
Чтобы проверить, есть ли уже символ в подстроке, мы можем просканировать подстроку, что приведет к алгоритму O (n²). Но мы можем добиться большего.
Используя HashSet в качестве скользящего окна, можно проверить, можно ли использовать текущий символ в O (1).
Ниже приведены два способа реализации скользящего окна для уменьшения временной сложности с O (n³) до O (n²) и O (n) соответственно.
class Solution { public: int lenOfLongestSubstring(string s) { int ans = 0; for (int i = 0; i < s.length(); ++i) { for (int j = i; j < s.length(); ++j) { if (repeat(s, i, j)) { ans = max(ans, j-i+1); } } } return ans; } bool repeat (string s, int start, int end) { vector<int> chars(128); for (int i = start; i <= end; ++i) { char c = s[i]; chars[c]++; if (chars[c] > 1) { return false; } } return true; } };
Временная сложность: O(n²)
class Solution { public: int lengthOfLongestSubstring(string s) { vector<int> chars(128); int left = 0; int right = 0; int res = 0; while (right < s.length()) { char r = s[right]; chars[r]++; while (chars[r] > 1) { char l = s[left]; chars[l]--; left++; } res = max(res, right - left + 1); right++; } return res; } };
Сложность времени: O(n)
Следите за новостями, чтобы увидеть больше этих обучающих программ по алгоритмам.