Какие проверки и крайние случаи нужно предусмотреть при сопоставлении шаблона и строки?

Что проверяют

Умеете ли вы до кода уточнить синтаксис шаблона и перебрать граничные случаи. Обычно это задача про wildcard (? и *) или про упрощённые регулярки (. и *). Следом спрашивают сложность и почему наивная рекурсия не проходит.

Как отвечать

Сначала уточните условие: полное совпадение или поиск подстроки, что значит * (любая последовательность или повтор предыдущего символа), важен ли регистр, какие символы бывают в строке.

Граничные случаи, которые стоит проговорить вслух:

• пустые входы: пустой шаблон совпадает только с пустой строкой; * в wildcard и a* в регулярке совпадают с пустой строкой, а ? нет;
• звёздочки подряд: ** эквивалентна одной, их удобно схлопнуть заранее;
• звёздочка в начале и в конце: частый источник ошибок на индексах;
• шаблон длиннее строки: без * сразу False;
• *регулярка, начинающаяся с ``**: шаблон некорректен, договоритесь, как на него реагировать;
• регистр и юникод: для сравнения без учёта регистра str.casefold() надёжнее lower().

Решение: динамическое программирование по таблице (n + 1) × (m + 1), где ячейка отвечает, совпадает ли префикс строки длины i с префиксом шаблона длины j. Время и память O(n·m), память сжимается до двух строк таблицы. В Python ту же идею удобно записать рекурсией с @functools.cache. Для wildcard есть жадный вариант на двух указателях с откатом к последней звёздочке.

Если разрешена стандартная библиотека, назовите re.fullmatch, re.escape для пользовательского ввода и fnmatch.fnmatchcase для wildcard.

Где спотыкаются

Используют re.match, думая, что он проверяет всю строку. Он привязан только к началу: re.match("a", "ab") находит совпадение, нужен fullmatch.

Пишут рекурсию без мемоизации. На шаблоне вроде a*a*a*a*b против длинной строки из a время растёт экспоненциально.

Ошибаются с размером таблицы и базой: забывают строку для пустого префикса и то, что * в начале шаблона совпадает с пустой строкой.