Long pressed string
Задача: вы набираете имя на клавиатуре, которая иногда залипает и выводит символ несколько раз.
Необходимо проверить набранное имя с оригинальным и вернуть true, если возможно, что это было оригинальное имя, но с залипанием некоторых символов (возможно, было 0 залипаний), false — в противном случае.
Входные данные: origin — оригинальное имя, typed — набранное имя на клавиатуре. Обе строки содержат только прописные буквы английского алфавита: [‘a’,…,’z’].
Вывод: true/false
Примеры:
- Origin: “albert”,
Typed: “albert”
Output: true - Origin: “albert”,
Typed: “aaalberrt”
Output: true (“залипли” символы ‘a’ и ‘r’) - Origin: “lee”,
Typed: “lle”
Output: false (оригинальное имя содержит 2 символа ‘e’)
Разбор
Эта задачу довольно легко можно решить за 3 прохода:
- сначала мы собираем информацию формата символ -> количество послед.вхождений для обоих строк (origin, typed);
- затем проходим и сравниваем элементы такой коллекции. Если мы встретили отличный символ или символ в набранной строке, у ктр кол-во послед.вхождений меньше, чем в оригинальной строке, то сразу выводим false.
Однако мы можем оптимизировать алгоритм как по времени, так и по памяти. Воспользуемся методом двух указателей: 1й указатель будет идти по оригинальной строке, 2й по набранной.
А идея довольно простая: на каждой итерации, мы будем проверять, равны ли текущие символы в строках.
- eсли да, то мы увеличиваем оба указателя;
- в противном случае мы предполагаем, что мы встретили символ, ктр ‘залип’, т.е. текущий набранный символ должен быть равен предыдущему. Если же и эта проверка не пройдена, то мы смело выводим false.
Смотрите детали реализации методом 2х указателей ниже!
Реализация
Код с комментариями!
https://gist.github.com/unilecs/e13c78b00563a4ddef89cf1faa140c0f
