UniLecs #Task. Get Shortest Distance to Character
Published in
2 min readFeb 17, 2021
Разбор
Давайте разделим решение на 2 части:
- Сначала будем идти по массива от начала к концу и запоминать индекс последнего вхождения символа C и вычислять мин. дистанцию для каждого элемента строки.
- Затем сделаем тоже самое, только будем идти по массиву с конца к началу. И мин. дистанция для каждого элемента строки будет минимальным среди 2х подходов.
Алгоритм:
- Заведем пустой массив res размера строки, а также переменную prevIndex, где будем хранить индекс последнего вхождения символа C в строку S.
- Для 1го прохода иницируем prevIndex = -int.MaxValue — заведомо большим отрицательным значением.
- Проходим строку от начала к концу, если встречаем символ C, то сохраняем текущий индекс в prevIndex. На каждом шаге для i-го элемента строки сохраняем дистанцию от(до) символа C равную (i — prev).
- Прошли строку 1-й раз. Далее иницируем переменную prevIndex = int.MaxValue — заведомо большим положительным значением. Запускаем проход по строке 2й раз, но с конца к началу.
- Обновляем переменную prevIndex, если встретили символ C. Также на каждом шаге для i-го элемента строки сохраняем минимальную дистанцию от(до) символа C равную (prevIndex — i) и выбираем мин.значение, сравнивая со значением дистанции res[i] — найденной на 1-м проходе.
- Возвращаем результирующий массив res.
Детали реализации смотрите ниже в коде!
Реализация
