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); }
📝 Сохраните эту историю в Журнале.