Это связано с проблемой кода leetcode: https://leetcode.com/problems/reverse-string/solution/
Напишите функцию, которая переворачивает строку. Входная строка задается как массив символов char [].
Не выделяйте дополнительное пространство для другого массива, вы должны сделать это, изменив входной массив на месте с помощью O (1) дополнительной памяти.
Пример:
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Решение 1:
class Solution:
def reverseString(self, s):
def helper(left, right):
if left < right:
s[left], s[right] = s[right], s[left]
helper(left + 1, right - 1)
helper(0, len(s) - 1)
Сложность времени: O (N) время выполнения N / 2 свопов. Сложность пространства: O (N) для сохранения стека рекурсии.
Решение2:
class Solution:
def reverseString(self, s):
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left, right = left + 1, right - 1
Сложность по времени: O (N) для замены N / 2 элемента. Сложность пространства: O (1), это постоянное пространственное решение.
Может кто-нибудь объяснить, почему сложность пространства в решении 2 равна O (1), а сложность пространства в решении 1 равна O (n)?
Это потому, что решение 1 требует вызова функции?
Заранее спасибо!