1. Обращение строки с помощью встроенных функций

  • Метод split() возвращает новый массив с каждым символом исходной строки в качестве подстроки.
  • Метод reverse() переворачивает массив на месте. Первый элемент массива становится последним, а последний элемент массива становится первым.
  • Метод join() объединяет все элементы массива в строку.
// Time Complexity = Possibly O(n+k)
// Since these are inbuilt methods, we can't be 100% sure of how 
// JavaScript is handling them. But since .reverse() involves
// traversing through an array, it possibly has time complexity 
// of O(n).
// So we can represent the time complexity as O(n+k), where k is a
// constant to heuristically denote the complexity of the other two 
// methods.
function reverseString(string) {
 return string.split('').reverse().join('')
}

2. Переверните строку с помощью убывающего цикла For

// Time Complexity = O(n)
function reverseString(string) {
var newString = '';
for (var i = string.length - 1; i >= 0; i--)
  newString += string[i];
return newString;
}

3. Обратить строку с помощью древовидной структуры данных.

Древовидная структура данных - это иерархическая структура данных, состоящая из узлов, соединенных ребрами. Он имеет следующие особенности:

  • В дереве есть один узел, называемый корнем. Дерево происходит из этого, и, следовательно, у этого узла нет никакого родителя.
  • У каждого узла есть только один родительский элемент, но может быть несколько дочерних.
  • Каждый узел связан со своими дочерними элементами через ребро.

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

Хотите прочитать эту историю позже? Сохранить в журнале.

Обычно, если бы мы выполняли операцию поиска с древовидной структурой данных, это было бы за логарифмическое время или O (log n), но в этом случае наша функция посещает каждый узел один раз, что приводит к линейной временной сложности или O (п).

// Time Complexity = O(n)
function reverseString(string) {
 if (string.length === 1) return string;
 let parentNode = Math.floor(string.length / 2);
 let leftPart = string.substring(0, parentNode)
 let rightPart = string.substring(parentNode);
 return reverseString(rightPart) + reverseString(leftPart);
}

📝 Сохраните эту историю в Журнале.