Поиск элементов массива, начинающихся с заданного префикса

Условие

Необходимо пройти по массиву строк и собрать все те элементы, у которых начало совпадает с переданным префиксом. Функция принимает два аргумента: массив строк words и строку‑префикс prefix. Результатом должна быть новая коллекция (массив, список и т.п.) только с теми строками, которые начинаются с prefix. Если ни одна строка не удовлетворяет условию, возвращается пустой массив.

Пример

words = ["apple", "apricot", "banana", "application", "cat"]
prefix = "ap"
# результат: ["apple", "apricot", "application"]

Требования

• Сравнение должно быть чувствительным к регистру (строка "Apple" не считается начинающейся с префикса "ap").
• Время работы должно быть линейным относительно количества элементов в массиве.
• Память используется только для хранения результата и нескольких вспомогательных переменных.

Подсказка: используйте метод startswith (или аналогичный) для проверки начала строки.

Ответ

Пройдите по words один раз и оставьте строки, для которых startswith(prefix) возвращает True. Сравнение чувствительно к регистру, порядок элементов и повторы сохраняются.

Реализация:

def by_prefix(words, prefix):
    return [word for word in words if word.startswith(prefix)]

Для примера получится ['apple', 'apricot', 'application']. При отсутствии совпадений возвращается [], а пустой префикс подходит любой строке. При фиксированной длине префикса время O(n); в общем случае O(n·m), где m — длина проверяемого префикса. Дополнительная память O(k) для k результатов.