Я пытаюсь решить проблему LeetCode 3. Самая длинная подстрока без повторяющихся символов:
Учитывая строку
s
, найдите длину самой длинной подстроки без повторяющихся символов.Пример 1:
Ввод:
s = "abcabcbb"
Выход: 3
Пояснение: Ответ: «abc» длиной 3.
В этом случае я могу придумать только решение методом грубой силы, когда вы находите все возможные подстроки, проверяете, действительны ли они, а затем находите максимальную длину этих подстрок. Это то, что у меня есть до сих пор:
#returns true if there is a duplicate character
def count_characters(self,s):
for i in s:
if s.count(i)>1:
return True
return False
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
#generate list of all substrings
max_len = 0
for i in range(len(s)):
for j in range(i+1, len(s)+1):
substr = s[i:j]
if len(substr)>max_len and not self.count_characters(substr):
max_len = len(substr)
print(substr)
return max_len
Что мне следует сделать, чтобы пройти тесты с более длинными входными данными, чтобы не истечь тайм-аутом?
Попробуйте проходить по входной строке по одному символу, создавая по ходу подстроку. Для каждого символа проверьте, есть ли он уже в подстроке. Когда вы получите повтор, сохраните только что созданную подстроку. Затем начните новую подстроку, которая начинается после символа, дублированного в предыдущей подстроке.
Каждый раз, когда вы доходите до конца подстроки, перед ее сохранением проверьте, длиннее ли она существующей сохраненной подстроки.
вы можете проверить наличие дубликатов, выполнив len(set(substr)) == len(substr)
, большая часть кода выполняется на C, поэтому он будет быстрее, чем любой необработанный цикл, который вы когда-либо могли написать.
вы также можете выйти из внутреннего цикла, как только условие сообщит вам, что у вас есть повторяющийся символ, добавление дополнительных символов в эту строку не приведет к удалению повторяющегося символа.
Ответ ограничен размером алфавита: если ваша строка содержит только строчные английские буквы, то после 27 букв у вас обязательно будут повторяющиеся символы.
Таким образом, во внутреннем цикле достаточно зациклить до 26 букв общей сложностью O(N * 26)
.
Ваш подход не эффективен. Благодаря двум вложенным циклам выражение s[i:j]
вычисляется O(𝑛²) раз, а само это выражение имеет временную сложность O(𝑚), где 𝑚 — размер среза. Это приводит к общей сложности O(𝑛³).
Дело в том, что даже если вы нашли подстроку, содержащую повторяющиеся символы, вы все равно создадите более крупные подстроки, содержащие эту подстроку. Это пустая трата усилий. Вы можете подумать, что если у вас есть хорошая подстрока, вам нужно только проверить символ, который вы добавите к этой подстроке, чтобы убедиться, что подстрока все еще действительна. На самом деле вам даже не нужно создавать подстроку. Отслеживание его начальных/конечных индексов вместе с набором символов в нем может быть достаточным.
Эту проблему можно решить с временной сложностью O(𝑛).
Попытайтесь придумать эффективный алгоритм с учетом приведенного выше анализа.
Вот еще несколько советов, если они вам понадобятся:
раздвижное окно
индекс появления последнего символа, на каждый символ
И напоследок реализация спойлера:
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: last_occurence = {} # per character: last found index for it exclude = -1 # index before the current substring's start longest = 0 for i, ch in enumerate(s): exclude = max(exclude, last_occurence.get(ch, -1)) last_occurence[ch] = i longest = max(longest, i - exclude) return longest
спойлер очень крутой.
да, в пятницу я не знал, что это сработало
Вы можете следовать стандартному процессу решения раздвижного окна:
Это непосредственно приводит к линейному (O(N)
) решению следующим образом.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
curr = set()
l = ans = 0
for r, c in enumerate(s):
while c in curr:
curr.remove(s[l])
l += 1
curr.add(c)
ans = max(ans, r - l + 1)
return ans
Вам нужно найти решение без грубой силы. Они намеренно используют большие тестовые примеры, которые приведут к провалу грубой силы.