Я придумал решение для задачи Leetcode «Самая длинная подстрока без повторяющегося элемента», которая в основном основана на методе грубой силы. Для практики я также пытаюсь найти его сложность, но хотел бы получить некоторую обратную связь о том, как это сделать, так как я не настолько хорош в этом.
Код решения
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
## Brute force approach
if len(s) == 0:
return 0
orig_elts = [s[0]]
pre_length = 1
idx = 1
while idx <= len(s) - 1:
#print("This is idx", idx)
if s[idx] not in orig_elts:
orig_elts.append(s[idx])
pre_length = max(pre_length, len(orig_elts))
idx += 1
else:
pre_length = max(pre_length, len(orig_elts))
tmp_idx = orig_elts.index(s[idx])
orig_elts = orig_elts[tmp_idx + 1:]
return pre_length
Я полагаю, что сложность составляет O (n ^ 2) , поскольку пока l oop я прохожу через всю строку один раз, и это имеет сложность O (n) , а затем операция поиска, если s[idx] находится в orig_elts, занимает O (n) . Итак, я пришел к выводу, что алгоритм будет иметь O (n ^ 2) сложность.
Спасибо за любые отзывы или предложения о том, как рассчитать это. Подобные вопросы не являются моей сильной стороной, поэтому я стараюсь получить как можно больше практики.