Различные подходы к ее решению в JavaScript

Вы когда-нибудь ловили себя на том, что смотрите на строку, задаваясь вопросом, как изменить ее порядок? Сегодня мы рассмотрим множество подходов, которые можно использовать для ее решения, включая два указателя. Если вы не знакомы с двумя указателями, не волнуйтесь, это умный способ манипулирования массивами (и строками!), который включает в себя отслеживание двух индексов одновременно. И не волнуйтесь, я обещаю не вдаваться в объяснения (не удержался от каламбура). Так что сядьте поудобнее, расслабьтесь и давайте погрузимся!

Постановка задачи:

Напишите функцию, которая переворачивает строку.

Подход 1: грубая сила

  1. Мы можем создать пустую строку, затем перебрать входную строку от конца к началу и соединить каждый символ с новой строкой.
// ES6 Arrow Function
const reverseString = str => {
    let reversed = '';

    for(let i = str.length; i >= 0; i--) {
        reverseString += str[i];
    }

    return reverseString;
}

Временная сложность:O(N)

Пространственная сложность:O(N)

Подход 2: два указателя

  1. Мы можем использовать два указателя, один из которых начинается с начала строки, а другой — с конца.
  2. Мы меняем местами символы в каждом индексе, пока два указателя не встретятся посередине.
  3. Примечание.Элементы в каждом указателе меняются местами с помощью деструктуризации массива.
// ES6 Arrow Function
const reverseString = str => {
    let i = 0, j = str.length - 1;

    while(i <= j) {
        [str[i], str[j]] = [str[j], str[i]];
        i++;
        j--;
    }

    return str;
}

Временная сложность:O(N)

Пространственная сложность:O(1)

Примечание.В дополнение к подходу с двумя указателями в JavaScript есть два других метода решения этой проблемы: использование встроенных методов и использование рекурсии. Хотя оба этих метода имеют временную и пространственную сложность линейного порядка, наиболее эффективным методом является подход с двумя указателями. Тем не менее, для полноты картины решения для обоих этих методов также представлены ниже.

Подход 3. Встроенные методы

  1. JavaScript предоставляет встроенный метод reverse(), который можно использовать для обращения массива.
  2. Поскольку строки в JavaScript можно рассматривать как массивы символов, мы можем преобразовать строку в массив, перевернуть массив, а затем преобразовать его обратно в строку.
// ES6 Arrow Function
const reverseString = str => {
    return str.split('').reverse().join('');
}

Временная сложность:O(N)

Пространственная сложность:O(N)

Подход 4: рекурсия

Мы можем рекурсивно перевернуть подстроку, исключающую первый символ, а затем соединить первый символ в конце.

// ES6 Arrow Function
const reverseString = str => {
    if(str === '') return '';
    else return reverseString(str.substr(1)) + str.charAt(0);
}

Временная сложность:O(N)

Пространственная сложность:O(N)

И у вас есть это, ребята! Мы исследовали различные подходы, оптимизировали наши решения и, надеюсь, повеселились. Я надеюсь, что эта статья предоставила вам ценную информацию и помогла лучше понять различные подходы к решению этой проблемы. Удачного кодирования!