Я с трудом пытаюсь выяснить временную и пространственную сложность следующего Python3 решения этого вопроса: "По заданной строке определите, является ли она палиндромом, учитывая только буквы c букв и цифр и игнорируя случаи. "
def isPalindrome(s):
s = ''.join(filter(str.isalnum, s)).lower()
return s == s[::-1]
Мой мыслительный процесс выглядит следующим образом:
- Сложность времени: filter (): O (n) + join (): O (n) + lower (): O (n) + s [:: - 1]: O (n) = O (4n) = O (n)
- Сложность пространства: O (n), поскольку вы переназначаете значение s для себя, но все символы могут в конечном итоге быть действительными, поэтому в худшем случае s будет той же длины, что и изначально. Есть ли что-то еще, что мне не хватает в плане занимаемого пространства?
Есть ли способ улучшить любую из асимптотических c сложностей?