Задача: №44. Wildcard Matching
Сложность: hard

Учитывая входную строку s и шаблон p, реализуйте сопоставление шаблонов с подстановочными знаками с поддержкой:
- '?' — соответствует любому одному символу
- '*' — соответствует любой последовательности символов (включая пустую)

Сопоставление должно охватывать всю строку s.

Пример:

Input: s = "adceb", p = "*a*b" Output: true

👨‍💻 Алгоритм:

1⃣Создать двумерный булев массив dp размером (s.length + 1) × (p.length + 1), где dp[i][j] — true, если s[0..i-1] соответствует p[0..j-1].

2⃣Инициализировать базовые случаи:
- dp[0][0] = true
- dp[0][j] = true, если p[0..j-1] состоит только из * (иначе — false)

3⃣Заполнить таблицу:
- Если p[j-1] == s[i-1] или p[j-1] == '?' → dp[i][j] = dp[i-1][j-1]
- Если p[j-1] == '*' → dp[i][j] = dp[i][j-1] || dp[i-1][j]
- Иначе → dp[i][j] = false

😎 Решение:

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;

        for (int i = 1; i <= m; i++) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = dp[0][i - 1];
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = false;
                }
            }
        }

        return dp[n][m];
    }
}

Ставь 👍 и забирай 📚 Базу знаний