Описание испытания

Напишите функцию, которая переворачивает строку. Входная строка задается как массив символов s.

Вы должны сделать это, изменив входной массив на месте с O(1) дополнительной памятью.

Пример 1:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Пример 2:

Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Интуиция

Мы хотим перевернуть массив символов на месте, а это означает, что мы не можем использовать дополнительную память, например, для создания нового массива.
Для этого мы будем использовать подход с двумя указателями, где мы размещаем два указателя, i и j, на двух концах массива. Мы поменяем местами символы в этих указателях, чтобы перевернуть массив.

Подход

  1. Мы будем использовать два указателя, i и j, инициализированные соответственно началом и концом массива.
  2. Пока i меньше j, выполним следующие шаги:
  • Поменяйте местами символы в позициях i и j.
  • Переместите i на один шаг вперед (к середине), увеличив его.
  • Переместите j на один шаг назад (к середине), уменьшив его.
  • Мы продолжаем повторять вышеуказанные шаги, пока i не станет меньше или равно j. Когда я становится равным или большим, чем j, весь массив будет перевернут.

Сложность

  • Временная сложность:
    подход с двумя указателями работает за линейное время O(N), где N — длина массива символов. Это связано с тем, что каждый элемент заменяется не более одного раза.
  • Сложность пространства:
    Сложность пространства постоянна O(1), потому что мы не используем никакой дополнительной памяти, которая растет с размером входных данных. Мы изменяем данный массив на месте.
function reverseString(s: string[]): void {
  // Iterate from the beginning (i) and end (j) of the array towards the middle.
  for (let i = 0, j = s.length - 1; i < s.length / 2; i++, j--) {
    // Use a temporary variable (temp) to store the character at index i.
    const temp = s[i];

    // Replace the character at index i with the character at index j.
    s[i] = s[j];

    // Replace the character at index j with the character in the temporary variable (temp).
    s[j] = temp;
  }
  // At this point, the string array 's' contains the reversed string.
}