Разворот слов в строке

Средняя

medium , string , two pointers

06 February 2024

Описание задачи #

Необходимо написать функцию, которая будет переставлять слова в строке в обратном направлении. Слова в строке разделены пробелами, пробелов между слов может быть несколько, а также пробелы могут стоять в начале и конце исходной строки.

В итоговой строке слова должны быть разделены одним пробелом, а также не должно быть пробелов в начале и конце строки.

Ограничения #

Длина строки может быть в диапазоне от 1 до 10000
Строка содержит только буквы латинского алфавита, числа и пробелы.
В каждой строке есть как минимум одно слово

Примеры #

Входные данные: "the sky is blue"

Ответ: "blue is sky the"
Входные данные: " hello world "

Ответ: "world hello"
Входные данные: "a good example"

Ответ: "example good a"

Решение #

Данную задачу можно решить легким трюком: ответ мы получим, если избавимся от лишних пробелов, после перевернем каждое слово в строке, и в конце перевернем полностью всю строку. Давайте рассмотрим задачу на примере a good example.

Удаляем лишние пробелы внутри строки и получаем строку a good example
Далее переворачиваем каждое слово внутри строки и получаем строку a doog elpmaxe
Последним шагом переворачиваем всю строку и получаем требуемый результат example good a

Для реализации этого алгоритма нам потребуется решить следующие подзадачи:

Удаление лишних пробелов
Определение границ слов внутри строки
Переворот слова/строки в обратном направлении

Для удобства преобразуем входящую строку в массив byte (так как в ограничениях явно сказано, что в строке используются только)

Метод по удалению лишних пробелов trimSpaces вынесем в отдельную простую функцию.

Для определения границ слов нам достаточно посимвольно пройтись по строке:

Запоминаем индексы начала и конца строки (исходно startIdx = 0 и endIndex = 0).
Как только мы доходим до первого пробела, считаем это границей нужного нам слова и переворачиваем часть строки от startIdx до endIndex. Переносим наши startIdx и endIndex на следующий элемент строки.

Переворот строки мы также реализуем в виде отдельной простой функции reverseWord. Эта функция будет использоваться как для переворота отдельных слов внутри строки, так и для переворота целой строки.

Реализация #

package main

func reverseWords(s string) string {
	startIdx := 0
	endIdx := 0

	trimmed := trimSpaces([]byte(s))

	for startIdx < len(trimmed) {
		for endIdx < len(trimmed) && trimmed[endIdx] != byte(' ') {
			endIdx++
		}

		reverseWord(trimmed, startIdx, endIdx-1)
		startIdx = endIdx + 1
		endIdx++
	}

	reverseWord(trimmed, 0, len(trimmed)-1)

	return string(trimmed)
}

func reverseWord(s []byte, i, j int) {
	for i < j {
		s[i], s[j] = s[j], s[i]
		i++
		j--
	}
}

func trimSpaces(bStr []byte) []byte {
	isStart := true
	j := 0
	for i := 0; i < len(bStr); i++ {
		if bStr[i] == byte(' ') && isStart {
			continue
		}

		bStr[j] = bStr[i]
		j++
		isStart = bStr[i] == byte(' ')
	}

	if bStr[j-1] == byte(' ') {
		j--
	}

	return bStr[:j]
}

const reverseWord = (s: string, i: number, j: number): string => {
    const strArr = [...s]

    while (i < j) {
        const temp = strArr[i]
        strArr[i] = strArr[j]
        strArr[j] = temp
        i++
        j--
    }

    return strArr.join('')
}

const trimSpaces = (s: string): string => {
    let isStart = true
    let j = 0
    let strArr = [...s]

    for (let i = 0; i < strArr.length; i++) {
        if (strArr[i] == ' ' && isStart) {
            continue
        }

        strArr[j] = strArr[i]
        isStart = strArr[i] == ' '
        j++
    }

    if (strArr[j - 1] == ' ') {
        j--
    }

    return strArr
        .join('')
        .substring(0, j)
}

export const reverseWords = (s: string): string => {
    let startIdx = 0
    let endIdx = 0

    let trimmed = trimSpaces(s)

    while (startIdx < trimmed.length) {
        while (endIdx < trimmed.length && trimmed[endIdx] !== ' ') {
            endIdx++
        }

        trimmed = reverseWord(trimmed, startIdx, endIdx - 1)
        startIdx = endIdx + 1
        endIdx++
    }

    return reverseWord(trimmed, 0, trimmed.length - 1)
}

Оценка сложности #

По времени

Для решения задачи нам потребуется несколько раз посимвольно пройтись по строке:

Удаление лишних пробелов.
Переворот каждого слова в строке
Переворот целой строки

Итоговая сложность равна O(n).

По памяти

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

В общем случае оценить память можно в O(n).

Оригинал задачи на Leetcode

Algorithmics