6. Wildcard Matching

«Шаблон свободен в своих предположениях, но строг в проверке фактов».
— Брайан Керниган

Задача о сопоставлении с маской (Wildcard Matching / Glob Matching, LeetCode 44) — близкая родственница 5. Regular Expression Matching, но с принципиально иной алгоритмической философией.

Если в регулярных выражениях квантификатор * жестко привязан к предыдущему символу, то в масках файлов (Globbing) символы * и ? самостоятельны:

• ? сопоставляется ровно с одним любым символом.
• * сопоставляется с любой последовательностью символов (включая пустую).

Для Senior Go-разработчика эта задача интересна тем, что наряду с классическим двумерным DP она допускает потрясающее инженерное решение: жадный алгоритм с откатом (Greedy with Backtracking Pointer), работающий за $O(M + N)$ в среднем и требующий строго $O(1)$ памяти (0 аллокаций в куче).

1. Постановка задачи и практическое применение

Условие:
Даны строка s и шаблон p. Реализовать сопоставление с поддержкой ? и * для всей строки целиком.

Вход:  s = "adceb", p = "*a*b"
Выход: true
Пояснение: первая '*' заменяет пустую строку, вторая '*' заменяет "dce". Итог: "adceb".

В реальных бэкенд-системах этот алгоритм используется ежесекундно:

• Маршрутизация HTTP-запросов в API Gateway (Nginx, Traefik, Envoy): маски путей /api/v1/users/*/orders.
• Политики авторизации IAM (AWS IAM, GCP IAM, Kubernetes RBAC): правила прав доступа arn:aws:s3:::my-bucket/*.
• Файловый глоббинг в Go: стандартные пакеты path.Match и path/filepath.Glob.

2. Подход 1: Динамическое программирование ($O(M \cdot N)$)

Определим $dp[i][j]$: совпадает ли префикс $s[0 \dots i-1]$ с префиксом $p[0 \dots j-1]$.

Правила переходов:

1. Символы равны или p[j-1] == '?':
   $$dp[i][j] = dp[i-1][j-1]$$
2. Шаблон содержит * (p[j-1] == '*'):
   Звездочка может либо поглотить 0 символов (смотрим налево по паттерну: $dp[i][j-1]$), либо поглотить текущий символ строки $s[i-1]$ (смотрим вверх по строке: $dp[i-1][j]$):
   $$dp[i][j] = dp[i][j-1] \;\lor\; dp[i-1][j]$$

3. Подход 2: Идиоматичный Go — Жадный алгоритм с откатом ($O(1)$ памяти)

В отличие от регулярок, в Wildcard звездочка не зависит от контекста. Это позволяет применить жадную эвристику:

1. При встрече * мы жадно предполагаем, что она заменяет пустую строку (0 символов). Мы запоминаем позицию звездочки (starIdx) и текущую позицию в строке (matchIdx), а указатель паттерна сдвигаем вперед.
2. Мы продолжаем идти вперед, пока символы совпадают.
3. Если мы натыкаемся на несовпадение, но ранее встречали *, наше первоначальное предположение было неверным! Мы производим локальный откат (rollback): звездочка обязана поглотить на один символ больше. Мы увеличиваем matchIdx++, сбрасываем i = matchIdx, а j возвращаем на позицию сразу за звездочкой (starIdx + 1).
4. Если несовпадение возникло, а звездочки в истории не было — строки не совпадают (false).

flowchart TD
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:2px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    Start["Сравнение s[i] и p[j]"]:::entry --> CheckMatch{"Символы равны<br/>или p[j] == '?'"}:::warning

    CheckMatch -- "Да" --> IncBoth["Прямой шаг:<br/>i++, j++"]:::success

    CheckMatch -- "Нет" --> CheckStar{"p[j] == '*'?"}:::warning
    CheckStar -- "Да (Встретили звезду)" --> SaveStar["Запоминаем:<br/>starIdx = j<br/>matchIdx = i<br/>j++ (жадно 0 символов)"]:::process

    CheckStar -- "Нет" --> CheckHistory{"Была ли звезда ранее?<br/>starIdx != -1"}:::warning
    CheckHistory -- "Да (Откат)" --> Rollback["Откат: звезда берет еще 1 символ<br/>matchIdx++<br/>i = matchIdx<br/>j = starIdx + 1"]:::warning
    CheckHistory -- "Нет" --> Fail["Возврат false"]:::error
  

4. Реализация на Go 1.22+ ($O(1)$ памяти)

package wildcard

// IsMatchWildcard проверяет совпадение строки s с шаблоном p (поддержка '?' и '*').
// Временная сложность: O(M + N) в среднем, O(M * N) в худшем патологическом случае.
// Пространственная сложность: O(1) — 0 аллокаций в куче.
func IsMatchWildcard(s string, p string) bool {
    i, j := 0, 0
    starIdx := -1
    matchIdx := 0

    lenS, lenP := len(s), len(p)

    for i < lenS {
        // 1. Символы совпадают или в паттерне стоит одиночный wildcard '?'
        if j < lenP && (p[j] == '?' || p[j] == s[i]) {
            i++
            j++
        // 2. Встретили '*': фиксируем контрольную точку и жадно предполагаем 0 символов
        } else if j < lenP && p[j] == '*' {
            starIdx = j
            matchIdx = i
            j++
        // 3. Несовпадение, но есть сохраненная звездочка: откат назад
        } else if starIdx != -1 {
            j = starIdx + 1
            matchIdx++
            i = matchIdx
        // 4. Несовпадение при отсутствии звездочек в истории
        } else {
            return false
        }
    }

    // Пропускаем оставшиеся хвостовые звездочки в шаблоне
    for j < lenP && p[j] == '*' {
        j++
    }

    // Строка сопоставлена, если шаблон пройден до самого конца
    return j == lenP
}

5. Mechanical Sympathy: Почему жадный подход убивает DP в продакшене?

Для API Gateway, обрабатывающего 100 000 RPS, переход от DP к жадному алгоритму снижает нагрузку на процессорные ядра на порядок и полностью ликвидирует скачки хвостовой задержки (p99 latency spikes), вызываемые сборщиком мусора Go.

6. Вопросы для собеседования

Итог кластера «DP на строках»

Мы завершили ключевой строковый блок:

1. Теория: Внутреннее устройство строк в Go (StringHeader), безопасность памяти с strings.Clone и разница между байтами и рунами.
2. Дуальность: Математическая связь $\text{EditDistance} = |S_1| + |S_2| - 2 \cdot \text{LCS}$ и архитектура алгоритма Майерса в Git.
3. LCS: Канонический разбор таблицы для "abcde" и "ace" со сжатием памяти до $O(\min(M, N))$.
4. Комбинаторика: Distinct Subsequences с обратным проходом (0/1 Knapsack паттерн) за $O(N)$ памяти.
5. Автоматы и ReDoS: Регулярные выражения (RE2 / Thompson NFA) с гарантированным $O(M \cdot N)$ против PCRE-уязвимостей.
6. Жадный глоббинг: Wildcard Matching со сведением задачи к 4 регистрам CPU и нулевым аллокациям.

В следующем кластере мы перенесем идеи динамического программирования на графовые структуры и древовидные иерархии: 1. Теория. DP на деревьях.