Разворот гласных в строке

Легкая

easy , string , two pointers

19 January 2024

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

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

В строке могут встречаться следующие гласные: a, e, i, o, и u как в верхнем, так и в нижнем регистре.

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

В строке может быть от 1 до 3 * 10⁵ символов
Строка состоит из печатных ASCII символов
Символы могут быть в верхнем и нижнем регистре

Примеры #

Входные данные: hello

Ответ: holle
Входные данные: algorithmics

Ответ: ilgirothmacs
Входные данные: ab

Ответ: ab

Решение #

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

dict := map[rune]struct{}{
    'a': {},
    'e': {},
    'i': {},
    'o': {},
    'u': {},
    'A': {},
    'E': {},
    'I': {},
    'O': {},
    'U': {},
}

const dict = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'])

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

Теперь нужно реализовать разворот гласных. Для этого заведем два указателя:

leftIdx равен нулю
rightIdx равен индексу последнего символа встроке

Чтобы правильно реализовать разворот, мы будем поочередно двигать левый и правый индексы, пока каждый из них не будет указывать на гласную букву. Как только это произойдет, поменяем буквы местами и будем повторять этот алгоритм до тех пор, пока leftIdx < rightIdx.

Реализация #

package reverse_vowels_of_string

func reverseVowels(s string) string {
	dict := map[rune]bool{
		'a': true,
		'e': true,
		'i': true,
		'o': true,
		'u': true,
		'A': true,
		'E': true,
		'I': true,
		'O': true,
		'U': true,
	}

	leftIdx := 0
	rightIdx := len(s) - 1

	sRunes := []rune(s)

	for leftIdx < rightIdx {
		left := sRunes[leftIdx]
		right := sRunes[rightIdx]

		if dict[left] == false {
			leftIdx++
		} else if dict[right] == false {
			rightIdx--
		} else {
			sRunes[leftIdx], sRunes[rightIdx] = sRunes[rightIdx], sRunes[leftIdx]
			leftIdx++
			rightIdx--
		}
	}

	return string(sRunes)
}

export const reverseVowels = (s: string): string => {
    const dict = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'])

    let leftIdx = 0
    let rightIdx = s.length - 1

    const chars = [...s]

    while (leftIdx < rightIdx) {
        const left = chars[leftIdx]
        const right = chars[rightIdx]

        if (!dict.has(left)) {
            leftIdx++
        } else if (!dict.has(right)) {
            rightIdx--
        } else {
            const tmp = chars[leftIdx]
            chars[leftIdx] = chars[rightIdx]
            chars[rightIdx] = tmp
            leftIdx++
            rightIdx--
        }
    }

    return chars.join('')
}

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

По времени

Так как мы перебираем все элементы массива один раз, сложность равна O(n).

По памяти

При приведении типов мы создаем новую переменную со строкой, поэтому сложность по памяти линейная — O(n).

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

Algorithmics