Ограничения:

  • 0 <= s.length, p.length <= 2000
  • s содержит только строчные латинские буквы.
  • p содержит только строчные английские буквы, '?' или '*'.

Решение

Решение для сопоставления шаблона с подстановочными знаками включает создание двумерного логического массива dp, где dp[i][j] представляет, совпадают ли первые i символов входной строки (s) с первыми j символами шаблона (p) с заданными условиями подстановочных знаков. Затем массив заполняется с помощью вложенного цикла for, в котором реализована логика сопоставления символов и подстановочных знаков.

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
//Metehan Homriş
var isMatch = function isMatch(s, p) {
  let dp = new Array(s.length + 1);
  for (let i = 0; i < dp.length; i++) {
    dp[i] = new Array(p.length + 1).fill(false);
  }
  dp[0][0] = true;

  // Fill the first row for patterns that starts with '*'
  for (let j = 1; j <= p.length; j++) {
    if (p[j - 1] === '*') {
      dp[0][j] = dp[0][j - 1];
    }
  }

  // Fill the rest of the table
  for (let i = 1; i <= s.length; i++) {
    for (let j = 1; j <= p.length; j++) {
      if (p[j - 1] === '?' || p[j - 1] === s[i - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else if (p[j - 1] === '*') {
        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
      }
    }
  }

  return dp[s.length][p.length];
}

Функция принимает два параметра, s и p, которые представляют входную строку и шаблон соответственно. Он инициализирует двумерный логический массив dp размером (s.length + 1) x (p.length + 1) и заполняет его значением false. Первая строка и столбец массива — это особые случаи, которые необходимо обрабатывать отдельно. Первая строка представляет случай, когда входная строка пуста, а первый столбец представляет случай, когда шаблон пуст.

Первый цикл обрабатывает особый случай, когда шаблон начинается с «*». Он устанавливает значение dp[0][j] как истинное, если значение dp[0][j-1] истинно. Это связано с тем, что «*» может соответствовать любой последовательности символов, включая пустую последовательность.

Вложенный цикл, начинающийся с i=1 и j=1, заполняет остальную часть таблицы. Цикл сравнивает текущий символ во входной строке с текущим символом в образце. Если они совпадают, значение dp[i][j] устанавливается равным значению dp[i-1][j-1]. Если текущим символом в шаблоне является '?', он соответствует любому символу, поэтому значение dp[i][j] устанавливается равным значению dp[i-1][j-1]. Если текущим символом в шаблоне является '*', он может соответствовать любой последовательности символов, включая пустую последовательность, поэтому мы можем установить dp[i][j] как истину, если либо dp[i][j-1], либо dp[i-1][j] истинны. Это связано с тем, что '*' может соответствовать любой последовательности символов, включая пустую последовательность, поэтому он может либо соответствовать текущему символу во входной строке, либо не соответствовать ему вообще.

Наконец, функция возвращает значение dp[s.length][p.length], представляющее результат сопоставления шаблона с подстановочными знаками. Если это значение истинно, это означает, что вся входная строка соответствует шаблону, а если ложно, это означает, что входная строка не соответствует шаблону.

Автор Метехан Хомриш

Дополнительные материалы на PlainEnglish.io.

Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord.

Повысьте узнаваемость и признание вашего технического стартапа с помощью Circuit.