Хеш-таблицы

Восстановить цифры

Восстановить оригинальные цифры из английского описания

Средний

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

Описание (LeetCode)

Дана строка s, содержащая неупорядоченное английское представление цифр от 0 до 9. Нужно вернуть цифры в порядке возрастания.

Пример 1:

s = "owoztneoer"

Результат:

"012"

Пояснение:

Строка "owoztneoer" содержит неупорядоченное описание цифр 0, 1, 2: "zero", "one", "two".

Пример 2:

s = "fviefuro"

Результат:

"45"

Пояснение:

Строка "fviefuro" содержит описание цифр 4, 5: "four", "five".

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

1 <= s.length <= 10⁵
s[i] - один из символов из строки "egfihonsrutwvxz"
гарантируется, что s валидна

Решение

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

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

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

Перейдите на Premium, чтобы продолжить

Разблокируйте доступ к этой статье и всем остальным материалам с NowInterview Premium

Перейти на Premium